题目
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
解题
本题目要求解集中不能包含重复组合
比如输入: candidates = [2,5,2,1,2], target = 5, 不能同时出现[2,2,1]和[2,1,2]
所以要排序candidates=[1,2,2,2,5];
其次,可以把回溯看成一个N叉树，横向就是for循环，纵向就是递归
横向不能取重复元素，纵向可以取重复元素
为了使得横向不能取if( i>0&&candidates[i]==candidates[i-1]) continue;
但是这样会把纵向的重复也给去掉了
也就是说纵向的i=startIndex可以取,
下图中，不同颜色，代表不同递归层次（纵向）。相同的颜色，代表同一个for循环(横向)
所以只需要if(i>startIndex&&candidates[i]==candidates[i-1]) continue;,就可以使得横向去重，纵向不去重
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(vector<int>& candidates,int target,int sum,int startIndex){ if(sum==target){ res.push_back(path); return; } else if(sum>target) return; for(int i=startIndex;i<candidates.size();i++){ if(i>startIndex&&candidates[i]==candidates[i-1]) continue; path.push_back(candidates[i]); sum+=candidates[i]; backtracing(candidates,target,sum,i+1); sum-=candidates[i]; path.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); backtracing(candidates,target,0,0); return res; } };
方法二：
class Solution { public: vector<vector<int>> res; vector<int> path; void dfs(vector<int>&candidates,int target,vector<bool>& used,int sum,int start){ if(sum==target){ res.push_back(path); return; } else if(sum>target) return; for(int i=start;i<candidates.size();i++){ if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false) continue; sum+=candidates[i]; used[i]=true; path.push_back(candidates[i]); dfs(candidates,target,used,sum,i+1); path.pop_back(); used[i]=false; sum-=candidates[i]; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<bool> used(candidates.size(),false); sort(candidates.begin(),candidates.end()); dfs(candidates,target,used,0,0); return res; } };
java
class Solution { List<List<Integer>> res=new LinkedList<>(); List<Integer> path=new LinkedList<>(); void dfs(int[] candidates,int target,boolean[] used,int startIndex,int sum){ if(sum==target){ res.add(new LinkedList<>(path)); return; }else if(sum>target) return; for(int i=startIndex;i<candidates.length;i++){ if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false) continue; path.add(candidates[i]); used[i]=true; dfs(candidates,target,used,i+1,sum+candidates[i]); used[i]=false; path.remove(path.size()-1); } } public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); boolean[] used=new boolean[candidates.length]; dfs(candidates,target,used,0,0); return res; } }
