y*******d
发帖数: 1674 | 1 LC 39
code 如下
两处不明白
1. 为什么要先排序？
2. 为什么helper(res, target-candidates[i], tmp, candidates, i); 是i不是
i+1？？
多谢指点
public List> combinationSum(int[] candidates, int target) {
List> res = new ArrayList>();
if (candidates == null || candidates.length == 0) {
return res;
}
Arrays.sort(candidates);
helper(res, target, new ArrayList(), candidates, 0);
return res;
}
void helper(List> res, int target, List tmp, int[
] candidates, int start) {
if (target == 0) {
res.add(new ArrayList(tmp));
}
for (int i = start; i < candidates.length && target >= candidates[i]
; i++) {
tmp.add(candidates[i]);
helper(res, target-candidates[i], tmp, candidates, i);
tmp.remove(tmp.size()-1);
}
} | e*******s
发帖数: 1979 | 2 排序reduce search path, 从小到大, 如果当前sum > target 立即返回
【在 y*******d 的大作中提到】
: LC 39
: code 如下
: 两处不明白
: 1. 为什么要先排序？
: 2. 为什么helper(res, target-candidates[i], tmp, candidates, i); 是i不是
: i+1？？
: 多谢指点
: public List> combinationSum(int[] candidates, int target) {
: List> res = new ArrayList>();
: if (candidates == null || candidates.length == 0) {
| e*******s
发帖数: 1979 | 3 是i应为每个number可以用多次 参考2, 2, 3 target 7
【在 y*******d 的大作中提到】
: LC 39
: code 如下
: 两处不明白
: 1. 为什么要先排序？
: 2. 为什么helper(res, target-candidates[i], tmp, candidates, i); 是i不是
: i+1？？
: 多谢指点
: public List> combinationSum(int[] candidates, int target) {
: List> res = new ArrayList>();
: if (candidates == null || candidates.length == 0) {
| y*******d
发帖数: 1674 | 4 好像不光是减少search path
我试了如果不排序似乎结果也不对
【在 e*******s 的大作中提到】
: 排序reduce search path, 从小到大, 如果当前sum > target 立即返回
| e*******s
发帖数: 1979 | 5 因为排序后面的code依赖于排序假定, 减少了search path.
如果不排序就是full branch DFS, 慢很多而已 不会没结果
【在 y*******d 的大作中提到】
: 好像不光是减少search path
: 我试了如果不排序似乎结果也不对
| c********t
发帖数: 5706 | 6 我觉得leetcode答案和你的code都有问题
题目要求The solution set must not contain duplicate combinations.
你试试
[2,7,3,2,7,2]
7
排序是为了去重，去重的部分你缺了啊。
从i开始是为了能重复用一个元素 （有点绕，就是我自己这个元素想用多少次都可以，
但不能再用和我相同的另一个元素）
【在 y*******d 的大作中提到】
: LC 39
: code 如下
: 两处不明白
: 1. 为什么要先排序？
: 2. 为什么helper(res, target-candidates[i], tmp, candidates, i); 是i不是
: i+1？？
: 多谢指点
: public List> combinationSum(int[] candidates, int target) {
: List> res = new ArrayList>();
: if (candidates == null || candidates.length == 0) {
| c********t
发帖数: 5706 | 7 对，也有这个作用。不过排不排序，如果sum>target都要返回，因为all numbers are
positive. 不同的是中间的循环，可以提前跳出。
还有不排序也可以，只要把输入用hashset去重。
【在 e*******s 的大作中提到】
: 排序reduce search path, 从小到大, 如果当前sum > target 立即返回
|
|
