自己解法
标准的回溯加剪枝，思路很清晰，但是在细节上出了点小问题，一个是递归的时候应该用i+1,用成了start + 1。还有就是这个重复的剪枝，一开始没想明白，画了下树形图，就是减去相邻树枝中重复的部分，这个一定要放到回溯操作后，放在前面的话会导致不同层的相同元素也被过滤。
class Solution {
List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<Integer> res = new ArrayList<>();
dfs(candidates, target, 0, res);
return output;
}
public void dfs(int[] candidates, int target, int start, List<Integer> res) {
if (target == 0) {
output.add(new ArrayList(res));
return;
}
for (int i = start; i < candidates.length; i++) {
if (target < candidates[i]) {
return;
}
res.add(candidates[i]);
dfs(candidates, target - candidates[i], i + 1, res);
res.remove(res.size() - 1);
// 减去重复的枝
while (i < candidates.length - 1 && candidates[i + 1] == candidates[i]) {
i++;
}
}
}
}
官方解法
查看比较多的这个解法，剪重复的枝，是在前面剪的，不过是i > index以后，也就是在同层遍历的时候进行剪枝。
class Solution {
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates.length == 0){
return result;
}
Arrays.sort(candidates);
comSum2(candidates,target,0,new LinkedList<Integer>());
return result;
}
public void comSum2(int[] candidates, int target, int index, LinkedList<Integer> trace){
//满足结束条件
if(target == 0){
result.add(new LinkedList(trace));
return ;
}
if(target > 0){
//选择列表，并加上约束
for(int i = index; i<candidates.length; i++){
//如果以当前结点为头结点的所有组合都找完了，那么下一个与他他相同的头结点就不用去找了。
if(i > index && candidates[i] == candidates[i - 1]) continue;
//做出选择
trace.add(candidates[i]);
comSum2(candidates,target - candidates[i],i+1,trace);
//撤销选择
trace.removeLast();
}
}
}
}
网友评论