回溯 | Java | LeetCode 39, 40, 131 做题总结(未完)
Java
Arrays.sort(数组) //排序
不讲究顺序的解答，都可以考虑一下排序是否可行。
39. 组合总和
错误解答
在写的时候需要注意，sum -= candidates[i];很重要，也是回溯的一部分。
解答重复了。是因为回溯的for循环理解错了。
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0, 0);return res;}List<Integer> path = new ArrayList<>();public void backtracking(int[] candidates, int target, int sum, int index) {if(sum > target) {return;}if(sum == target) {res.add(new ArrayList<>(path));return;}for(int i=0; i<candidates.length; i++) {sum += candidates[i];path.add(candidates[i]);backtracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size()-1);}}
}
正确
- 修改成下面这样就对了
优化
不讲究顺序的解答，都可以考虑一下排序是否可行。
剪枝要先排序。
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return res;}List<Integer> path = new ArrayList<>();public void backtracking(int[] candidates, int target, int sum, int index) {if(sum == target) {res.add(new ArrayList<>(path));return;}for(int i=index; i<candidates.length; i++) {sum += candidates[i];if (sum > target) break;path.add(candidates[i]);backtracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size()-1);}}
}
40.组合总和II
想得太简单了……
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);back(candidates,target,0,0);return res;}List<Integer> path = new ArrayList<>();void back(int[] candidates, int target, int sum, int index) {if(sum > target) return;if(sum == target) {res.add(new ArrayList(path));}for(int i=index; i<candidates.length; i++) {path.add(candidates[i]);sum+=candidates[i];back(candidates,target,sum,index+1);sum-=candidates[i];path.remove(path.size()-1); }}
}