Problem overview
The method CombinationSum2 receives an int[] named candidates, which may contain repeated values, and an int named target. It returns every distinct combination of candidates that adds up to target as a List<List<int>>. Each candidate can be used at most once, so a value that appears twice in the array can appear up to twice in one combination. Two combinations are the same when they hold the same numbers the same number of times, whichever copies were used. Each combination is written in ascending order, and the combinations come in lexicographic order. If nothing adds up to the target, the result is an empty list.
For [10,1,2,7,6,1,5] and target = 8 the result is [[1,1,6],[1,2,5],[1,7],[2,6]]. The combination [1,7] can be made with either 1 but appears once. For [2,5,2,1,2] and 5 it is [[1,2,2],[5]], and for [2,3] and 4 it is []: 2 + 3 is 5, and the 2 can't be used twice.
Approach: sort, choose the next number, skip repeated values
The search builds a combination one number at a time. A call receives start, the first index it may still use, remaining, the amount the combination still needs, and current, the numbers chosen so far. When remaining is 0, current adds up to the target and a copy of it is saved. Otherwise a loop tries each index i from start on as the next number: add candidates[i], call itself with i + 1 and remaining - candidates[i], and remove the number again.
Three ideas keep the search correct and small:
- Sorting. After
Array.Sort, equal numbers are neighbours, combinations come out in ascending order, and larger numbers sit at the end, which allows an early exit. - Passing
i + 1, noti. The next number must come from after the one just taken, so each candidate is used at most once. A version that allows reuse passesi. - Skipping repeated values. Inside one call, every turn of the loop picks a different number for the next position. A second copy of a value that the previous turn already tried would rebuild the same combinations, so the loop skips
candidates[i]wheni > startand it equalscandidates[i - 1]. The first copy, ati == start, is taken: that is how[1,1,6]gets its second 1.
Because the array is sorted, once candidates[i] is larger than remaining, every later number is larger too, and the loop stops with break.
Step by step
- Sort
candidateswithArray.Sort. - Create
result, a list of lists. - Start the search with
Backtrack(candidates, 0, target, new List<int>(), result): nothing chosen, all oftargetstill needed, every index available. - Return
result. - Write
Backtrack. Ifremaining == 0, add a copy ofcurrentand return. All candidates are at least 1, so adding another number could only overshoot. - Loop
ifromstartto the end of the array. - Skip repeats: if
i > startandcandidates[i] == candidates[i - 1],continue. - Stop early: if
candidates[i] > remaining,break. - Choose with
Add, recurse withi + 1and the reduced remainder, and undo withRemoveAt(current.Count - 1).
The solution in C#
class Solution {
public List<List<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
List<List<int>> result = new List<List<int>>();
Backtrack(candidates, 0, target, new List<int>(), result);
return result;
}
public void Backtrack(int[] candidates, int start, int remaining, List<int> current, List<List<int>> result) {
if (remaining == 0) {
result.Add(new List<int>(current));
return;
}
for (int i = start; i < candidates.Length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remaining) {
break;
}
current.Add(candidates[i]);
Backtrack(candidates, i + 1, remaining - candidates[i], current, result);
current.RemoveAt(current.Count - 1);
}
}
}
The C# details worth knowing:
- The snapshot.
List<int>is a reference type, and the search keeps changingcurrent.new List<int>(current)copies its numbers into a new list, so the saved combination doesn't change later. breakagainstcontinue.continueends this turn of the loop and goes on with the nexti, which suits the repeat check.breakleaves the loop altogether, which is right for "too big", because the sorted array has nothing smaller further on.Array.Sortsorts the caller's array in place.
Complexity
Time: O(n * 2^n) in the worst case. With n candidates there are at most 2^n ways to pick some of them, and copying a combination takes up to n steps. The sort adds O(n log n). In practice the search is much smaller: it only continues through distinct combinations whose sum doesn't exceed target, and the break cuts the rest.
Space: beyond the answer, O(n): the combination being built and one call per number in it.
Edge cases and common mistakes
- No combination.
[2,3]with target 4 returns an empty list. - Single candidate equal to the target.
[5]with target 5 returns[[5]]. - Many copies of one value.
[1,1,1,1]with target 2 returns[[1,1]]: one combination, however many pairs of 1s could make it. - Skipping too much. The check
i > 0instead ofi > startforbids a second copy even when the first copy is in the combination. For[10,1,2,7,6,1,5]and 8,[1,1,6]is lost and the result is[[1,2,5],[1,7],[2,6]]. - Not skipping. For
[1,1,7]and 8,[1,7]is returned twice. - Passing
iinstead ofi + 1. A candidate can then be chosen again and again: for[2,3]and 4 the result is[[2,2]], but there is only one 2.
Testing
[10,1,2,7,6,1,5]with 8 gives[[1,1,6],[1,2,5],[1,7],[2,6]].[2,5,2,1,2]with 5 gives[[1,2,2],[5]].[2,3]with 4 gives[].[1,1,7]with 8 gives[[1,7]].[1,1,1,1]with 2 gives[[1,1]].[5]with 5 gives[[5]].
