Problem overview
The method combinationSum2 receives candidates, an array of integers that may contain duplicates, and a target. It returns every distinct combination of candidates that adds up to target. Each candidate can be used at most once, so a value that appears twice in the array can appear up to twice in a combination. Two combinations are the same when they hold the same numbers the same number of times, whichever copies they use: with [1, 1, 7] and a target of 8, the first 1 with the 7 and the second 1 with the 7 make one combination, [1, 7], listed once.
Each combination is written in ascending order, and the combinations are returned in lexicographic order. In the example [10, 1, 2, 7, 6, 1, 5] with target 8, the result is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. [1, 2, 5] comes before [1, 7] because at the second number 2 is smaller than 7. When nothing adds up to the target, the answer is an empty array: for [2, 3] with target 4 it is [], because 2 + 3 is 5 and the 2 can't be used twice.
Approach: backtracking over sorted candidates
Sort the candidates first. Then a call receives start, the first index it may still use, remaining, the amount the combination still needs, and current, the combination so far. If 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 deeper call starts at
i + 1. In a version of the problem where a number may be used again and again, the call would start ati. Here every candidate is used at most once, so the next number must come from after this one. - Repeated values are skipped. Inside one call, each turn of the loop picks a different next number. If
i > startandcandidates[i]equalscandidates[i - 1], the previous turn already tried that value, and trying it again would build the same combinations a second time. Ati == startthe number is the first one this call tries, so it is taken even when it equals the one before it. That is how[1, 1, 6]gets its second 1. - The loop stops early. The candidates are sorted, so when
candidates[i]is bigger thanremaining, every later one is bigger too. The loop canbreak.
The search is exponential: with n candidates there are up to 2^n ways to pick some of them. The sorted order and the early stop keep it much smaller in practice, because the calls only build distinct combinations whose sum is at most target.
Step by step
- Sort a copy. Parameters are constants in Swift, so declare a new constant also named
candidatesset tocandidates.sorted(). - Create
result, an empty[[Int]]. - Create
current, an empty[Int]. - Start the search with
backtrack(candidates, 0, target, ¤t, &result): every index may be used, and all of the target is still needed. - Return
result. - Declare the helper
backtrackwithcandidates,start,remainingand the twoinoutparameterscurrentandresult. - Check for success:
if remaining == 0. - Save and return. Append
currenttoresultandreturn. Every candidate is at least 1, so adding anything more would go past the target. - Loop with
ioverstart..<candidates.count. - Skip repeats with
if i > start && candidates[i] == candidates[i - 1] { continue }. - Stop when too big with
if candidates[i] > remaining { break }. - Choose
candidates[i]: append it tocurrent. - Recurse with
candidates,i + 1,remaining - candidates[i],¤tand&result. - Undo the choice with
current.removeLast().
The solution in Swift
class Solution {
func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
let candidates = candidates.sorted()
var result = [[Int]]()
var current = [Int]()
backtrack(candidates, 0, target, ¤t, &result)
return result
}
func backtrack(_ candidates: [Int], _ start: Int, _ remaining: Int, _ current: inout [Int], _ result: inout [[Int]]) {
if remaining == 0 {
result.append(current)
return
}
for i in start..<candidates.count {
if i > start && candidates[i] == candidates[i - 1] {
continue
}
if candidates[i] > remaining {
break
}
current.append(candidates[i])
backtrack(candidates, i + 1, remaining - candidates[i], ¤t, &result)
current.removeLast()
}
}
}
The Swift details worth a closer look:
- Shadowing the parameter.
let candidates = candidates.sorted()is allowed: the new constant hides the parameter.sorted()returns a new array, so the caller's array stays as it was. inoutand&. Arrays are values and are copied when passed. Markingcurrentandresultasinoutlets the helper change the caller's arrays, and every call site marks them with&.- Value semantics.
result.append(current)stores a copy. The laterappendandremoveLastcalls oncurrentcan't alter the combinations already saved. continueandbreak.continueskips the rest of the current turn and goes to the nexti.breakleaves theforloop altogether. This is the difference between the two checks: a repeat only skips one number, while a number that is too big ends the loop.
Complexity
Time: O(n · 2^n) in the worst case, for n candidates. There are at most 2^n ways to pick some of them, and copying a combination into result takes up to n steps. The sort adds O(n log n). In practice the search is far smaller: it skips repeated values and stops at the first number that is too big.
Space: O(n) besides the answer: the combination being built, and one call per number in it.
Edge cases and common mistakes
- No skip. For
[10, 1, 2, 7, 6, 1, 5]with target 8, the result becomes[[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]]:[1, 2, 5]and[1, 7]are listed twice, once for each 1. - Skipping with
i > 0. The second 1 is then never taken after the first, and[1, 1, 6]disappears: the same input returns[[1, 2, 5], [1, 7], [2, 6]]. The test must bei > start. - Recursing with
iinstead ofi + 1. The same candidate is used again. For[2, 3]with target 4 the method returns[[2, 2]], but there is only one 2. - Forgetting to sort. The skip, the early
breakand the order of the answer all rely on the sorted array.
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]].[1, 1, 1, 1]with target 2 gives[[1, 1]].[5]with target 5 gives[[5]].
