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.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
solve(new ArrayList<>(), candidates, 0, target);
return ans;
}
void solve(List<Integer> curr, int[] cand, int idx, int target) {
if (target == 0) {
ans.add(new ArrayList<>(curr));
return;
}
for (int i = idx; i < cand.length; i++) {
if (target < cand[i])
break;
if (i > idx && cand[i] == cand[i - 1])
continue;
curr.add(cand[i]);
solve(curr, cand, i + 1, target - cand[i]);
curr.remove(curr.size() - 1);
}
}
}