Problem overview
The function combinationSum receives an IntArray of distinct numbers, candidates, and a target. It returns every combination of candidates that adds up to target. Each number can be used as many times as you like, and two combinations are the same when they use the same numbers the same number of times, whatever the order. Each combination is written in ascending order, and the combinations are returned in lexicographic order.
For candidates = [2, 3, 6, 7] and target = 7 the answer is [[2, 2, 3], [7]]. For candidates = [5, 2, 3] and target = 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], even though the candidates arrive unsorted. For candidates = [2] and target = 1 there is no combination, so the result is an empty list.
Approach: build a combination one number at a time
This is a search over choices. At each point you hold a partial combination and the amount still needed, remaining. You pick the next number, subtract it from remaining, and continue. If remaining reaches 0, the partial combination is complete and gets recorded. After exploring a choice you remove the number again and try the next one: that is backtracking.
Two decisions keep the answer free of duplicates and in the right order:
- Sort the candidates first. Then every combination is built in ascending order, and trying candidates from smallest to largest produces the combinations in lexicographic order.
- Only move forward. A call receives a starting index
iand may use candidates fromion, never earlier ones. The same number can repeat, because the recursive call starts fromj, notj + 1.[2, 2, 3]is found;[3, 2, 2]can't be, because after a 3 the search never goes back to a 2.
Sorting also allows a cut: if candidates[j] is larger than remaining, every later candidate is larger still, so the loop can stop with break.
The search is exponential. A combination has at most target / m numbers, where m is the smallest candidate, and each is one of n candidates, so the time is O(n^(target / m)) in the worst case.
Step by step
The outer function:
- Sort in place with
candidates.sort(). - Create
resultas an emptymutableListOf<List<Int>>(). Each combination is a list of numbers, so the result is a list of lists. - Start the search with
backtrack(candidates, target, 0, mutableListOf(), result): nothing is chosen yet, all oftargetis still needed and every candidate may be used. - Return
result, which the helper filled.
The helper, backtrack:
- Record a finished combination. When
remaining == 0, the numbers incurrentadd up to the target. Add a copy,current.toList(), andreturn. Every candidate is at least 2, so adding more would overshoot anyway. - Loop over the allowed candidates with
for (j in i until candidates.size). - Stop at a number that is too big. If
candidates[j] > remaining,break. - Choose it by adding
candidates[j]tocurrent. - Recurse with
remaining - candidates[j]and the same indexj, which lets the number be used again. - Undo the choice with
current.removeAt(current.size - 1), so the loop can try the next candidate from the same state.
The solution in Kotlin
class Solution {
fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
candidates.sort()
val result = mutableListOf<List<Int>>()
backtrack(candidates, target, 0, mutableListOf(), result)
return result
}
fun backtrack(candidates: IntArray, remaining: Int, i: Int, current: MutableList<Int>, result: MutableList<List<Int>>) {
if (remaining == 0) {
result.add(current.toList())
return
}
for (j in i until candidates.size) {
if (candidates[j] > remaining) {
break
}
current.add(candidates[j])
backtrack(candidates, remaining - candidates[j], j, current, result)
current.removeAt(current.size - 1)
}
}
}
The Kotlin details worth a closer look:
toList()makes a snapshot.currentkeeps changing during the search. If the code addedcurrentitself, every entry ofresultwould be the same list object, and by the end it would show whatevercurrentholds then, an empty list.toList()copies the numbers into a new list.ListversusMutableList. The return typeList<List<Int>>is a read-only view. Inside,resultandcurrentareMutableLists, which haveaddandremoveAt. ThemutableListOf()in the first call has its element type inferred from the parameter type.removeAtversusremove. On aMutableList<Int>,removeAt(index)removes by position.remove(x)removes the first element equal tox, which is a different operation, soremoveAtis the right call for undoing the last choice.i until candidates.sizeis a range that stops before the size, sojis always a valid index.sort()on anIntArraysorts in place and returns nothing, so the caller's array is reordered. Usesorted()or copy the array first if the original order matters.
Complexity
Time: exponential, O(n^(target / m)) in the worst case, where n is the number of candidates and m the smallest one. The depth of the search is at most target / m, and each level may try up to n candidates. The break and the forward-only index prune much of that.
Space: O(target / m) besides the answer: the combination being built and one call per number in it. The copies stored in result are the output itself.
Edge cases and common mistakes
- No combination.
[2]with target 1 gives[]: the loop breaks at once because 2 is bigger than 1. - Reusing a number.
[2]with target 4 gives[[2, 2]]. Recursing withj + 1would forbid it. - Duplicate combinations. Starting every loop at 0 instead of
iwould produce[2, 3]and[3, 2]as separate answers. - Forgetting the copy. Adding
currentinstead ofcurrent.toList()fillsresultwith references to one list that ends up empty. - Forgetting to undo. Without
removeAt, the numbers pile up incurrentand later combinations contain leftovers. - Unsorted input. Without sorting, the output order is wrong and the
breakwould cut off candidates that still fit.
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],target = 1gives[].candidates = [2],target = 4gives[[2, 2]].candidates = [7, 3, 5],target = 12gives[[3, 3, 3, 3], [5, 7]].candidates = [2, 3],target = 6gives[[2, 2, 2], [3, 3]].
