Problem overview
The method combinationSum2 receives candidates, an IntArray that may contain duplicates, and an integer target. It returns every distinct combination of candidates that adds up to target. Each candidate can be used at most once, but a value that appears twice in the array can appear twice in one combination.
Two combinations are the same when they hold the same numbers the same number of times, whichever copies were used. With [1,1,7] and a target of 8, the first 1 plus the 7 and the second 1 plus the 7 are the single combination [1, 7], listed once. Each combination is written in ascending order, and the combinations are in lexicographic order: the first position where two of them differ decides which comes first.
For candidates = [10,1,2,7,6,1,5] and target = 8, the answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. When no combination works, as with [2,3] and a target of 4, the method returns an empty list.
Approach: sorted backtracking that skips repeated values
Sort candidates first. Then a recursive helper builds a combination one number at a time. A call knows start, the first index it may still use, remaining, how much the combination still needs, and current, the combination 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: add candidates[i], recurse with i + 1 and the smaller remaining, and remove the number again.
Three details turn this into the right answer:
- Recursing with
i + 1. The deeper call starts after the number just chosen, so each candidate is used at most once. Starting atiwould allow a number to be chosen again and again. For[2,3]with target 4, that mistake returns[[2, 2]]where the right answer is empty. - Skipping repeated values. Inside one call, every turn of the loop picks a different candidate for the next number. If
candidates[i]equalscandidates[i - 1]andi > start, that value was already tried in this call, and trying it again would build the same combinations a second time. Ati == startthe number is the first one the call tries, so it is taken even when it equals its left neighbour. That is how[1, 1, 6]gets its second 1. - Stopping early. Because the array is sorted, once
candidates[i]is bigger thanremaining, every later candidate is bigger too, and the loop can stop withbreak.
Sorting also gives the required order: the loop tries smaller numbers first, so the combinations come out in lexicographic order.
Step by step
- Sort
candidatesin place withsort(). Equal values become neighbours. - Create
resultas amutableListOf<List<Int>>(). - Start the search with
backtrack(candidates, 0, target, mutableListOf(), result): from index 0, needing all oftarget, with an empty combination. - Return
result. - Declare
backtrackwithcandidates,start,remaining,currentandresult. - Check
remaining == 0: nothing is needed any more. - Save a copy with
current.toList()and return. Every candidate is at least 1, so adding another one would pass the target. - Loop
ioverstart until candidates.size. Starting atstartmakes a combination take its numbers in index order. - Skip repeats: if
i > startandcandidates[i] == candidates[i - 1],continue. - Break when too big: if
candidates[i] > remaining, leave the loop. - Choose the number by adding it to
current. - Recurse with
i + 1andremaining - candidates[i]. - Undo the choice with
removeAt(current.size - 1).
The solution in Kotlin
class Solution {
fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
candidates.sort()
val result = mutableListOf<List<Int>>()
backtrack(candidates, 0, target, mutableListOf(), result)
return result
}
fun backtrack(candidates: IntArray, start: Int, remaining: Int, current: MutableList<Int>, result: MutableList<List<Int>>) {
if (remaining == 0) {
result.add(current.toList())
return
}
for (i in start until candidates.size) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue
}
if (candidates[i] > remaining) {
break
}
current.add(candidates[i])
backtrack(candidates, i + 1, remaining - candidates[i], current, result)
current.removeAt(current.size - 1)
}
}
}
Kotlin details worth knowing:
sort()on anIntArrayworks in place and returns nothing, so the caller's array ends up sorted.- The copy matters.
currentis one list that keeps changing.result.add(current.toList())stores a snapshot with the numbers it holds right now, instead of a reference to the list that is emptied again as the search backs out. continueandbreakboth apply to the nearestforloop:continuegoes on with the nexti, andbreakleaves the loop.- The return type is the read-only
List<List<Int>>, while the object returned is aMutableListof lists, which is allowed.
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. In practice the search is far smaller, because it only builds distinct combinations whose sum so far does not pass target.
Space: O(n) besides the answer: the combination being built and one call for each number in it.
Edge cases and common mistakes
- No combination.
[2,3]with target 4 gives[], and[5]with target 3 also gives[]. - Single candidate.
[1]with target 1 gives[[1]]. - Several equal values.
[2,5,2,1,2]with target 5 gives[[1, 2, 2], [5]]: there are three 2s, and the combination with two of them appears once.[1,1,1,1]with target 2 gives[[1, 1]]. - Duplicates of the pair.
[1,1,7]with target 8 gives[[1, 7]]. Without the skip, the result is[[1, 7], [1, 7]], and on the main example it is[[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]], which also breaks the order. - Reusing a number. Recursing with
iinstead ofi + 1lets the main example produce[1, 1, 1, 1, 1, 1, 1, 1], a combination that uses the same 1 over and over, and many other wrong ones. - Many equal values. With one hundred 1s and a target of 30, the answer is a single combination of thirty 1s.
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]].
