Problem overview
The function combinationSum2 receives a slice candidates, which may contain repeated numbers, and an integer 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 candidates 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. With candidates = [1, 1, 7] and target = 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1 7], listed once. The numbers of each combination are in ascending order, and the combinations are returned in lexicographic order: the first position where two combinations differ decides which one comes first. If nothing adds up to the target, the result is empty.
For [10, 1, 2, 7, 6, 1, 5] and a target of 8 the answer is [[1 1 6] [1 2 5] [1 7] [2 6]]. Sorted, the candidates are [1 1 2 5 6 7 10]. The combination [1 1 6] uses both 1s, and [1 2 5] comes before [1 7] because 2 is smaller than 7 at the second position. For [2, 5, 2, 1, 2] and a target of 5 the answer is [[1 2 2] [5]]. For [2, 3] and a target of 4 it is empty, because the 2 can't be used twice.
Approach: sort, then pick the next number in a loop
The lesson uses backtracking. First sort candidates. A call to backtrack gets start, the first index it may still use, remaining, the amount the combination still needs, and current, the combination built so far. When remaining is 0, current adds up to the target, so the call saves a copy of it. Otherwise a loop tries each index i from start on as the next number: add candidates[i], recurse with i + 1 and remaining - candidates[i], then remove the number again.
Three details make it correct and fast:
- Recurse with
i + 1, noti. When a number may be reused, the deeper call starts at the same index. Here every candidate is used at most once, so the next number comes from further right. Passingiwould let the search use one 1 over and over, and on the first example it would return combinations such as[1 1 1 1 1 1 1 1]. - Skip repeated values in the loop. Inside one call, each turn of the loop picks a different next number. A second copy of the same value would rebuild the same combinations. So the loop skips
candidates[i]wheni > startand it equalscandidates[i-1]. Ati == startthe number is the first one this call tries, so it is taken, and that is how[1 1 6]gets its second 1. - Stop when a number is too big. The candidates are sorted, so once
candidates[i]is bigger thanremaining, every number after it is too big as well, and the loop canbreak.
Step by step
- Sort
candidateswithsort.Ints. Equal numbers become neighbours, the combinations come out in ascending order, and the loop can stop early. - Create
resultas an empty[][]int. - Start the search with
backtrack(candidates, 0, target, []int{}, &result): any index may be used, all of the target is still needed, the combination is empty, and the helper gets the address ofresult. - Return
resultafter the call. - Write the helper
backtrackwith the parameterscandidates,start,remaining,currentandresult *[][]int. - Check for a finished combination:
if remaining == 0. - Save a copy of
currentwithappend([]int{}, current...)and return. Every candidate is at least 1, so adding more would pass the target. - Loop with
ifromstartto the end of the slice. Starting atstartkeeps each combination in index order, so no set of indices is built twice. - Skip repeats: when
i > startandcandidates[i] == candidates[i-1], usecontinue. - Stop at the first number that is too big: when
candidates[i] > remaining, usebreak. - Choose the number by appending it to
current. - Recurse with
i+1andremaining-candidates[i]. - Undo the choice with
current = current[:len(current)-1].
The solution in Go
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
result := [][]int{}
backtrack(candidates, 0, target, []int{}, &result)
return result
}
func backtrack(candidates []int, start int, remaining int, current []int, result *[][]int) {
if remaining == 0 {
*result = append(*result, append([]int{}, current...))
return
}
for i := start; i < len(candidates); i++ {
if i > start && candidates[i] == candidates[i-1] {
continue
}
if candidates[i] > remaining {
break
}
current = append(current, candidates[i])
backtrack(candidates, i+1, remaining-candidates[i], current, result)
current = current[:len(current)-1]
}
}The Go details worth a closer look:
- The copy matters.
currentshares its backing array with the slices of other calls and keeps changing.append([]int{}, current...)builds a new slice that no later call can overwrite. - A pointer to the result.
appendmay return a slice with a new backing array, so the helper writes the new slice back through*result, wherecombinationSum2can see it. - Sorting changes the caller's slice.
sort.Intsworks in place, so after the call a caller's[10, 1, 2, 7, 6, 1, 5]is[1 1 2 5 6 7 10]. - Undoing with a slice expression.
current[:len(current)-1]drops the last element without allocating. The nextappendreuses that slot, which is safe because the saved copy is separate. - Empty result. The result starts as
[][]int{}, so when nothing matches the function returns an empty slice that prints as[], notnil.
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 takes up to n steps. Sorting adds O(n log n). In practice the search is much smaller, because it only builds distinct combinations whose sum stays within the target.
Space: O(n) beyond the answer: the combination being built and one call per number in it.
Edge cases and common mistakes
- No skip line. On the first example, the search without the repeat check returns
[[1 1 6] [1 2 5] [1 7] [1 2 5] [1 7] [2 6]], where[1 2 5]and[1 7]appear twice. - Comparing with
i > 0. Writingi > 0instead ofi > startalso skips the second 1 of[1 1 6]. The first example then returns only[[1 2 5] [1 7] [2 6]], and[2, 5, 2, 1, 2]with a target of 5 returns[[5]], losing[1 2 2]. - Forgetting to sort. The repeat check compares neighbours and the
breakassumes ascending order. If the first example is searched without sorting, the 10 at index 0 triggers thebreakat once and the search finds nothing. - Using a value twice when it appears once.
[2, 3]with a target of 4 returns[]. - Many equal values.
[1, 1, 1, 1]with a target of 2 returns just[[1 1]], one combination, not one for every pair of 1s. - Single candidate.
[3]with a target of 3 gives[[3]], and with a target of 4 gives[].
Testing
[10, 1, 2, 7, 6, 1, 5], target 8 gives[[1 1 6] [1 2 5] [1 7] [2 6]].[2, 5, 2, 1, 2], target 5 gives[[1 2 2] [5]].[2, 3], target 4 gives[].[1, 1, 7], target 8 gives[[1 7]].[1, 1, 1, 1], target 2 gives[[1 1]].
