Problem overview
The function combinationSum2 receives a list of integers candidates, which may contain duplicates, and a target. It returns every distinct combination of candidates that adds up to target. Each candidate is used at most once, so a number that appears twice in the list 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 they use. In [1, 1, 7] with target 8, the first 1 with the 7 and the second 1 with the 7 form one combination, [1, 7], and it is returned once. Each combination is written in ascending order, and the combinations are 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 answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. For [2, 3] and target 4 it is []: 2 + 3 is 5, and the 2 can't be used twice.
Approach: sorted backtracking with a skip rule
Sort candidates. A search call receives start, the first index it may still use, remaining, what the combination still needs, and current, the combination built so far. When remaining is 0, current adds up to the target, and a copy is saved. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and remaining - candidates[i], and removes the number again.
Three details make this correct and fast:
- The next call starts at
i + 1. In the version of this problem where numbers can be reused, the deeper call starts ati. Here every candidate may be used once, so the next number must come from after this one. - Repeats are skipped. The loop skips
candidates[i]wheni > startand it equalscandidates[i - 1]. Within one call, every turn picks a different next number, and a second copy of a value an earlier turn already picked would build the same combinations again. A copy is still taken ati == start, the first number the call tries, and that is how[1, 1, 6]gets its second 1. - The loop stops early. Because the list is sorted, the first candidate bigger than
remainingmeans every later one is too big as well, so the loop usesbreak.
Here is the search on [1, 1, 7] with target 8, with each line showing the depth of the call:
0| take 1 -> remaining 7
1| take 1 -> remaining 6
2| break at i=2 (7 > 6)
1| take 7 -> remaining 0
2| found [1, 7]
0| skip i=1 (1)
0| take 7 -> remaining 1The first call takes the first 1. The next call takes the second 1, finds that 7 is too big for the 6 that remains, and stops. Back one level, that call takes 7 instead, and the combination [1, 7] is found. At the top, the second 1 is skipped, because the first 1 was already tried as the first number. The trace for [2, 5, 2, 1, 2] with target 5 has the same shape, and finds [1, 2, 2] and [5].
Without the skip rule, [10, 1, 2, 7, 6, 1, 5] with target 8 returns [[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]], with [1, 2, 5] and [1, 7] listed twice.
Step by step
- Sort
candidatesin place withsort(). Repeats become adjacent, the output has the required order, and the loop can stop at the first number that is too big. - Create
result, an empty list of combinations. - Start the search with
self.backtrack(candidates, 0, target, [], result): from index 0, all of the target still needed, nothing chosen. - Return
result. The helper adds to this same list. - Declare the helper
backtrackwithcandidates,start,remaining,currentandresult. - Check for success. When
remaining == 0, the numbers incurrentadd up to exactly the target. - Save a copy and return.
current.copy()makes a snapshot, sincecurrentkeeps changing. Every candidate is at least 1, so adding another number would go past the target and there is nothing more to try. - Loop
ioverrange(start, len(candidates)). Starting atstartkeeps each combination in index order, so in ascending order, and no choice of positions is built twice. - Skip repeats with
continuewheni > startand the value equals the previous one. - Stop when the number is too big. If
candidates[i] > remaining, usebreak. - Choose the number by appending it to
current. - Recurse with
i + 1andremaining - candidates[i]. - Undo the choice with
current.pop(), so the loop can try the next candidate.
The solution in Python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
self.backtrack(candidates, 0, target, [], result)
return result
def backtrack(self, candidates, start, remaining, current, result):
if remaining == 0:
result.append(current.copy())
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remaining:
break
current.append(candidates[i])
self.backtrack(candidates, i + 1, remaining - candidates[i], current, result)
current.pop()
The Python details worth a closer look:
copy()is needed. The samecurrentlist is shared by every call and changed byappendandpop. Storing it directly would put the same list intoresultrepeatedly.sort()changes the caller's list. It sorts in place and returnsNone, so the list passed in comes back sorted.sorted(candidates)would give a new list and leave the original alone.breakversuscontinue.continueabandons one turn of the loop, andbreakabandons the whole loop. The skip for repeats is acontinue, because later numbers may still work. The size test can be abreakonly because the list is sorted.- The skip test at the start of the list. In
i > start and candidates[i] == candidates[i - 1],andstops at the first false test. Ati == startthe second test is never evaluated, so forstart == 0the code never readscandidates[-1], which in Python would silently read the last element.
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 sorted order keeps the search far smaller in practice: the calls only build distinct combinations whose sum is at most the target. With thirty 1s and target 30, for example, the helper is called 31 times, nowhere near the 2^30 ways of picking some of the thirty numbers.
Space: besides the answer, O(n): the combination being built and one active call per number in it.
Edge cases and common mistakes
- No combination.
[2, 3]with target 4 gives[], and so does[5]with target 3. - A single candidate.
[1]with target 1 gives[[1]]. - Only copies of one number.
[3, 3, 3]with target 6 gives[[3, 3]], and[1, 1, 1, 1]with target 2 gives[[1, 1]]: one combination, however many pairs of copies could make it. - Using a candidate more than once. Recursing with
iinstead ofi + 1turns the problem into the reuse version:[2, 3]with target 4 would return[[2, 2]]. - Forgetting the skip. The result then contains duplicates, as shown above.
- Using
i > 0for the skip. That would also skip the second 1 of[1, 1, 6]when it is the first number a call tries, so[1, 1, 6]would be lost: for[10, 1, 2, 7, 6, 1, 5]with target 8 the result is[[1, 2, 5], [1, 7], [2, 6]]. - Not sorting. The skip rule and the early
breakboth depend on a sorted list.
Testing
[10, 1, 2, 7, 6, 1, 5]with target 8 gives[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].[2, 5, 2, 1, 2]with target 5 gives[[1, 2, 2], [5]].[2, 3]with target 4 gives[].[1, 1, 7]with target 8 gives[[1, 7]].[3, 3, 3]with target 6 gives[[3, 3]].
