Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Examples
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints
1 <= candidates.length <= 100
Java Solution (Backtracking)
Copy class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
LinkedList<Integer> current = new LinkedList<>();
Arrays.sort(candidates);
backtrack(candidates, results, current, target, 0);
return results;
}
private void backtrack(int[] candidates, List<List<Integer>> results, LinkedList<Integer> current, int remaining, int start){
if(remaining == 0) {
results.add(new ArrayList<>(current));
return;
}
for(int i = start; i < candidates.length; i++) {
if(i > start && candidates[i] == candidates[i-1]) continue;
if(remaining - candidates[i] < 0) break;
current.add(candidates[i]);
backtrack(candidates, results, current, remaining - candidates[i], i+1);
current.removeLast();
}
}
}