Approach
Sort the candidates, then perform a depth-first search over their indices. Each recursive call chooses only a later index (i + 1), so an array occurrence can be used at most once. Equal values at different indices remain available as separate occurrences.
At a given recursion depth, skip a value when it equals the previous candidate at that same depth. This avoids exploring equivalent choices that would produce the same value combination, while still allowing repeated values from different indices to be chosen in a deeper call. Since all candidates are positive and sorted, a candidate larger than the remaining target can end the loop.
When the remaining target reaches zero, add a copy of the current path to the result. The copy is important because the path is backtracked and reused after that point.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
search(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void search(
int[] candidates,
int remaining,
int start,
List<Integer> path,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remaining) {
break;
}
path.add(candidates[i]);
search(candidates, remaining - candidates[i], i + 1, path, result);
path.remove(path.size() - 1);
}
}
}
The same-depth duplicate check prevents duplicate output combinations; advancing to i + 1 enforces the single-use rule for each occurrence. Sorting takes O(N log N). The search has O(2^N) worst-case time for N candidates, plus the cost of copying each returned combination; the recursion path uses O(N) auxiliary space, excluding output.