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 立即返回
|
|