Problem overview
The method combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] receives distinct integers and a target. It returns every combination of candidates that adds up to target. A candidate can be used any number of times, and two combinations are the same if they use the same numbers the same number of times, in any order. Each combination is written in ascending order, and the combinations are returned in lexicographic order: compare number by number, and the first difference decides.
For candidates = [2, 3, 6, 7] and target = 7, the answer is [[2, 2, 3], [7]]. For [5, 2, 3] and target 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], although the input isn't sorted. For [2] and target 1 it is [].
Approach: build combinations one number at a time
Brute force would generate every multiset of candidates and test its sum, which wastes almost all of its work. Backtracking builds a combination number by number and abandons it as soon as it can't work.
Keep a list current and a number remaining, the amount still needed. If remaining is 0, current is a complete combination. Otherwise, try each candidate as the next number: add it, search deeper with a smaller remaining, then remove it so the next candidate can take its place.
Two choices keep the output right:
- Sort the candidates first. Then a combination built left to right is in ascending order, and trying candidates from smallest to largest produces the combinations in lexicographic order, which is the order the answer needs.
- Only move forward. Each call receives an index
iand may use only candidates fromion, includingiitself, so a number can repeat. A combination is then built in exactly one order:[2, 2, 3]is found, and[3, 2, 2]never is. No duplicates arise, and there is nothing to filter out.
Sorting also allows an early exit. When a candidate is bigger than remaining, every later one is bigger too, so the loop can stop.
Step by step
- Sort a copy. Swift parameters are constants, so
let candidates = candidates.sorted()makes a new sorted array and hides the parameter. - Create
resultas an empty[[Int]], which collects the combinations. - Create
currentas an empty[Int], the combination being built. Nothing is chosen yet. - Start the search: call
backtrackwith the sorted candidates,targetas the amount still needed, 0 as the first index it may use, and¤tand&result. - Return
result. The helper added to the same array. - Declare
backtrackwithcandidates,remaining, the start indexi, andcurrentandresultasinoutparameters so every call shares them. - Test for a finished combination. If
remaining == 0, the numbers incurrentadd up to the target. - Record it and return.
result.append(current)stores a copy, and returning is right because every candidate is at least 2: adding more would overshoot. - Loop over the next choices with
for j in i..<candidates.count. - Stop at a number that is too big. If
candidates[j] > remaining,break. - Choose it: append
candidates[j]tocurrent. - Complete the choice: call
backtrackwithremaining - candidates[j]andjas the new start index. Passingjrather thanj + 1allows the same number again. - Undo the choice with
current.removeLast(), socurrentis what it was before this turn of the loop.
The solution in Swift
class Solution {
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
let candidates = candidates.sorted()
var result = [[Int]]()
var current = [Int]()
backtrack(candidates, target, 0, ¤t, &result)
return result
}
func backtrack(_ candidates: [Int], _ remaining: Int, _ i: Int, _ current: inout [Int], _ result: inout [[Int]]) {
if remaining == 0 {
result.append(current)
return
}
for j in i..<candidates.count {
if candidates[j] > remaining {
break
}
current.append(candidates[j])
backtrack(candidates, remaining - candidates[j], j, ¤t, &result)
current.removeLast()
}
}
}
The Swift details worth a closer look:
- Arrays are values.
result.append(current)stores a copy of the array as it is now. Aftercurrentis changed again, the stored combination stays the same. In a language where lists are references, you would copy by hand. In Swift the copy is automatic, and it is cheap until one side changes. inoutparameters.currentandresultare passed with&, and the helper changes the caller's arrays directly. That is why the helper returns nothing.sorted()versussort().sorted()returns a new array and leaves the original alone, which suits a constant parameter.sort()sorts in place and needs avar.- The range
i..<candidates.count. It is empty wheniequals the count, so the loop simply doesn't run. It would crash ifiwere larger than the count, butiis always an index of a candidate that was just used.
Complexity
Time: exponential. With n candidates, a target t and smallest candidate m, a combination has at most t / m numbers, and each is one of n candidates, so the bound is O(n^(t / m)). The break and the forward-only index cut this down a lot in practice, and the output itself can be large.
Space: O(t / m) besides the answer: the combination being built and one call per number in it.
Edge cases and common mistakes
- No combination.
[2]with target 1 returns[]: 2 is bigger than 1, so the loop breaks at once. - Unsorted input. Skipping the sort breaks both the output order and the early
break: with[5, 2, 3], after choosing 5 the amount left is 3, and the loop would stop at 5 at once, never trying 2 or 3, so[3, 5]would be missed. - Starting at 0 every time. Looping from 0 in each call builds
[2, 3]and[3, 2]as different lists, which gives duplicates. - Passing
j + 1. Then each number is used at most once, and[2, 2, 3]is lost. - Forgetting
removeLast().currentkeeps growing and every later combination begins with numbers it never chose. - Several candidates, one sum. For
[7, 3, 5, 2]and target 10, the answer has five combinations,[[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [3, 7], [5, 5]], including[5, 5], which uses one candidate twice.
Testing
[2, 3, 6, 7], target 7 gives[[2, 2, 3], [7]].[5, 2, 3], target 8 gives[[2, 2, 2, 2], [2, 3, 3], [3, 5]].[2], target 1 gives[].[3, 5], target 11 gives[[3, 3, 5]].[2, 3], target 6 gives[[2, 2, 2], [3, 3]].[7, 3, 5, 2], target 10 gives[[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [3, 7], [5, 5]].
