39. Combination Sum优化
来源:8-5 回溯法解决组合问题的优化
Ray_Lee_HZ
2019-12-08
老师,这段代码可以accept,但是only faster than 5.76% ,想不到什么优化方案了,老师有没有什么建议?
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return result;
}
Arrays.sort(candidates);
boolean hasAnswer = candidates[0] <= target;
if (!hasAnswer) {
return result;
}
for (int i = 0; i < candidates.length; i++) {
int selected = candidates[i];
if (selected > target) {
return result;
}
if (target == selected) {
List<Integer> oneAnswer = new ArrayList<>();
oneAnswer.add(target);
result.add(oneAnswer);
return result;
} else {
List<List<Integer>> lists = combinationSum(candidates, target - selected);
for (List<Integer> list : lists) {
list.add(selected);
Collections.sort(list);
if (!result.contains(list)) {
result.add(list);
}
}
}
}
return result;
}
写回答
1回答
-
liuyubobobo
2019-12-08
可以参考一下我的 Leetcode 题解代码仓的代码的思路,看看是否能看理解?
传送门:(C++ 版本) https://github.com/liuyubobobo/Play-Leetcode/blob/master/0039-Combination-Sum/cpp-0039/main.cpp
其中,最重要的递归函数,也就是发生回溯的函数,函数声明如下:
void solve(const vector<int> &candidates, int index, int target, vector<int>& cur_res, vector<vector<int>>& res)
这个函数的意思是,使用 candidates[index... n] 中的元素,凑出 target,
cur_res 存储当前找到的解;res 存储所有的解。
如果能理解这个思路,请在结合课程中的例题,仔细理解一下这类问题回溯法的过程是怎样的?
继续加油!:)
012019-12-11
相似问题