Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates =[10,1,2,7,6,1,5], target =8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]
与Combination Sum的区别在于，本题每次递归需要考虑重复元素，用while循环递归重复元素出现的次数；而Combination Sum每次递归只需要考虑两种情况，即放入该元素，或不放入该元素。
class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<Integer> ans = new ArrayList<Integer>(); Arrays.sort(candidates); backTrack(candidates, target, 0, ans, 0); return result; } public void backTrack(int[] candidates, int target, int start, List<Integer> ans, int sum){ if(sum == target ){ //found an answer List<Integer> new_ans = new ArrayList<Integer>(ans); //不能用List<Integer> new_ans = ans;这个只是创建了原List的一个引用 result.add(new_ans); } else if(start >= candidates.length || sum > target) return; //not found else{ int cnt = 0; //repeated times while(start+1 < candidates.length && candidates[start+1]==candidates[start]){ start++; cnt++; } // not choose current candidate backTrack(candidates,target,start+1,ans,sum); //choose current candidate List<Integer> backup = new ArrayList<Integer>(ans); int i = 0; for(i = 0; i <= cnt && sum <= target;i++){ backup.add(candidates[start]); sum += candidates[start]; backTrack(candidates,target,start+1,backup,sum); } } } private List<List<Integer>> result = new ArrayList<List<Integer>>(); }