Problem
Given an array of distinct combinations of candidates and a target integer, return all unique combinations where the chosen numbers sum to the target.Each number in
candidates may be used at most once.
The solution must not contain duplicate combinations.
Example(s)
Example 1
Input
candidates = [10,1,2,7,6,1,5]
target = 8Output
[[1,1,6],[1,2,5],[1,7],[2,6]]Example 2
Input
candidates = [2,5,2,1,2]
target = 5Output
[[1,2,2],[5]]Solution
This problem uses Backtracking. First, sort the array so duplicate values are adjacent. During backtracking, skip a value when it is the same as the previous value at the same recursion level to avoid duplicate combinations.Each candidate is used at most once, so the recursive call moves to
i + 1. When the remaining target becomes 0, the current combination is added to the result.
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] candidates, int target, int start,
List<Integer> current,
List<List<Integer>> result) {
// Target reached.
if (target == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < candidates.length; i++) {
// Skip duplicate values at the same level.
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// Stop when the current value exceeds the remaining target.
if (candidates[i] > target) {
break;
}
current.add(candidates[i]);
// Move to the next index because each number can be used once.
backtrack(candidates, target - candidates[i], i + 1,
current, result);
current.remove(current.size() - 1);
}
}
}Complexity
The time complexity is O(2n) in the worst case because each candidate can be included or excluded during backtracking.The space complexity is O(n) for the recursion stack and the current combination, excluding the space required to store the result.
