Problem overview
The function combinationSum receives a slice of distinct integers, candidates, and an integer 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 when they use the same numbers the same number of times, in any order: [2, 2, 3] and [3, 2, 2] count once. Each combination is written in ascending order, and the combinations are returned in lexicographic order, compared number by number. When nothing adds up to target, the result is an empty slice.
For candidates = [2, 3, 6, 7] and target = 7, the answer is [[2 2 3] [7]]: 2 + 2 + 3 and 7 alone. For candidates = [5, 2, 3] and target = 8, the answer is [[2 2 2 2] [2 3 3] [3 5]], even though the input isn't sorted. For candidates = [2] and target = 1, the answer is [].
Approach: build a combination one number at a time
This is a search problem, and backtracking fits it. Start with an empty combination and a remaining amount equal to target. At each step, try adding one candidate: subtract it from the remaining amount, build on the result, and then remove the candidate again to try the next one. When the remaining amount reaches exactly 0, the combination so far is a valid answer.
Three details make the search produce each combination once, in the required order:
- Sort the candidates first. Combinations are then built in ascending order, and the results come out in lexicographic order without a separate sort.
- Only move forward. After choosing the candidate at index
j, the next number is chosen from indexjonward, never from an earlier index. Indexjitself is allowed, because a number can repeat. This builds[2, 2, 3]and never[3, 2, 2], so no combination appears twice. - Stop early. Because the candidates are sorted, once one is bigger than the remaining amount, all later ones are too. The loop can
breakinstead of trying them.
The search is exponential. With n candidates, a smallest candidate m and a target t, a combination has at most t / m numbers, so the time is O(n^(t/m)) in the worst case. The constraints (at most 30 candidates, all at least 2, and a target of at most 40) keep real inputs small.
Step by step
The outer function
- Sort the candidates with
sort.Ints, which sorts in place in ascending order. - Create
resultas[][]int{}, a slice of combinations, each of which is a slice of ints. - Start the search with
backtrack: the candidates,targetas the amount still needed, 0 as the first usable index, an empty combination, and&result. The helper needs the address becauseappendcan return a new slice, and the new one has to be stored wherecombinationSumcan see it. - Return
result.
The helper backtrack
- Write the signature.
remainingis what the combination still needs,iis the first index it may use,currentis the combination built so far, andresultis a*[][]int, a pointer to the slice of combinations. It returns nothing. - Test for a full combination:
if remaining == 0. - Save a copy. Inside the test, append a copy of
currentto*resultand store the new slice back in*result. Thenreturn. Every candidate is at least 2, so adding more numbers would only go past the target. - Loop over the usable candidates:
for j := i; j < len(candidates); j++. - Stop at the first candidate that is too big: if
candidates[j] > remaining,break. - Choose it: append
candidates[j]tocurrentand keep the longer slice. - Recurse with
remaining-candidates[j]andjas the first index, so the same number can be chosen again.resultis already a pointer, so it is passed on as it is. - Undo the choice:
current = current[:len(current)-1]drops the last number, so the loop can try the next candidate in its place.
The solution in Go
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
result := [][]int{}
backtrack(candidates, target, 0, []int{}, &result)
return result
}
func backtrack(candidates []int, remaining int, i int, current []int, result *[][]int) {
if remaining == 0 {
*result = append(*result, append([]int{}, current...))
return
}
for j := i; j < len(candidates); j++ {
if candidates[j] > remaining {
break
}
current = append(current, candidates[j])
backtrack(candidates, remaining-candidates[j], j, current, result)
current = current[:len(current)-1]
}
}
Go details worth knowing:
- Why the copy matters. A slice is a small header that points at a backing array.
currentkeeps being shortened and extended over the same array, so a slice saved without copying changes later. This program savescurand then reuses its array:
It printsvar res [][]int cur := make([]int, 0, 4) cur = append(cur, 1, 2) res = append(res, cur) cur = cur[:1] cur = append(cur, 9) fmt.Println(res)[[1 9]], not[[1 2]].append([]int{}, current...)builds a new slice with its own array, so the saved combination stays as it was. - Why a pointer to the result. Go passes slices by value, so if
backtrackappended to its own copy ofresult, the caller wouldn't see the new length. Passing*[][]intand appending through*resultupdates the caller's variable. sort.Intssorts the caller's slice. After the call, the originalcandidatesslice is in ascending order:[5, 2, 3]becomes[2 3 5].- Empty result.
resultstarts as[][]int{}, so with no combinations the function returns an empty, non-nil slice, printed as[].
Complexity
Time: O(n^(t/m)) in the worst case, for n candidates, target t and smallest candidate m. The recursion is at most t / m levels deep, and each level can choose among at most n candidates. Sorting costs O(n log n) and is small next to the search. The break and the forward-only index prune the tree a lot in practice.
Space: beyond the answer itself, O(t / m): the combination being built and one call per number in it.
Edge cases and common mistakes
- No combination.
[3, 5]with target 7 returns an empty slice, with length 0.[2]with target 1 does too, because the only candidate is already bigger than the target and the loop breaks at once. - One number repeated.
[2]with target 4 returns[[2 2]]. Passingjto the recursive call allows the repeat. Passingj + 1would use each candidate once and miss this answer. - Starting the loop at 0 in every call. It finds
[2, 2, 3],[2, 3, 2]and[3, 2, 2]as separate answers. - Saving
currentwithout copying. The saved combinations are overwritten by later work, as the example above shows, and the final answer holds wrong or repeated rows. - Forgetting the sort. The
breakrelies on the candidates being in ascending order: on an unsorted slice like[5, 2, 3]it would stop at the first big number and skip smaller ones after it. - Forgetting the undo line. The combination keeps growing, and later candidates are added after numbers that should have been removed.
Testing
candidates = [2, 3, 6, 7],target = 7gives[[2 2 3] [7]].candidates = [5, 2, 3],target = 8gives[[2 2 2 2] [2 3 3] [3 5]].candidates = [2, 3, 5],target = 8gives[[2 2 2 2] [2 3 3] [3 5]].candidates = [2],target = 1gives[].candidates = [2],target = 4gives[[2 2]].candidates = [3, 5],target = 7gives[].
