Combination Sum

Q: Why do you recurse with i and not i + 1 in Combination Sum?

Recursing with i lets the next value be the same candidate again, which is how a value gets used more than once. Recursing with i + 1 moves past it, which turns the problem into the variant where each candidate is used at most once. The other half of the rule matters as much: never going back to an index before i keeps every combination in ascending order and stops duplicates.

MediumBacktracking

+10

You get a list candidates of different positive integers and a positive integer target. Find every combination of candidates whose values add up to exactly target, where each candidate may be used as many times as you like. Two combinations are the same when they use the same values the same number of times, so [2, 3, 3] and [3, 2, 3] count once.

Return each combination with its values in ascending order, and the combinations in lexicographic order: compare two combinations value by value from the left, and the one with the smaller value at the first difference comes first.

Function

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: the different values you may use, in any order, each as many times as you like
targetinteger: the total every combination must reach exactly
Returnsinteger-2d-array: every combination that sums to target, each in ascending order, listed in lexicographic order

Constraints

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
All values in candidates are different, in no particular order.
At least one combination reaches target, and at most 150 do.

Examples

Input: candidates = [6, 2, 3]target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Explanation: Four 2s make 8, and so do 2 + 3 + 3 and 2 + 6. All three start with 2, so the second value sets the order: 2, then 3, then 6. Without a 2 you only have 3s and 6s, and every mix of those is a multiple of 3, which 8 is not.

Input: candidates = [5, 3, 4]target = 11
Output: [[3, 3, 5], [3, 4, 4]]
Explanation: 3 + 3 + 5 and 3 + 4 + 4 both make 11. They match at the first value, and at the second the 3 is smaller than the 4, so [3, 3, 5] comes first. No mix of 4s and 5s alone makes 11.

Input: candidates = [4, 9]target = 9
Output: [[9]]
Explanation: 9 on its own is a combination. 4s give only 4, 8 and 12 on their way past 9, and 4 + 9 is already 13, so [9] is the only answer.

+12 hidden tests on Submit

Follow-up

Each candidate may now be used at most once, and candidates may hold repeated values. How do you change the search so that no combination appears twice?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every answer is a multiset of candidates, and the trap is building the same multiset more than once: picking 2, then 3, then 3 and picking 3, then 2, then 3 reach the same combination. The idea that cracks it is to build each combination in ascending order, so it has exactly one way to be built, and to sort the candidates so a branch stops the moment the next value is larger than what is left. The same ascending walk hands you the combinations in lexicographic order with no final sort.

Try every count of every candidate

Correct, but does not finish on the largest tests

Intuition

A combination is fully described by how many copies of each candidate it uses. For [6, 2, 3] and target 8, the answer [2, 3, 3] is one 2, two 3s and no 6. So one way to find every answer is to try every possible count for every candidate and keep the choices whose total is exactly target. A candidate c fits at most target / c times, so its count runs from 0 to that bound.

Picture a decision tree with one level per candidate, after sorting them. At level i you decide how many copies of the i-th value to take, and each leaf at the bottom is one full choice of counts. Each multiset has exactly one list of counts, so no combination is found twice. Trying the largest count first also gives the required order: when two answers first differ in the count of some value, the one with more copies still holds that small value where the other already holds a bigger one, so it comes first.

The trouble is the size of the tree. The number of leaves is the product of target / c + 1 over all candidates: for sorted [2, 3, 6] and target 8 that is 5 × 3 × 2 = 30 leaves for 3 answers. Every candidate larger than target / 2 doubles the leaves even though it fits at most once, so 40 such candidates alone mean 2^40, about 10^12, leaves. The large tests are built like that, and this approach cannot finish them.

Algorithm

Sort the candidates and make an array of counts, one per value.
Write choose(i, total), which fixes the count of the value at index i.
For k from target / nums[i] down to 0, set the count to k and call choose(i + 1, total + k × nums[i]).
When every value has a count, keep the combination if total equals target, writing each value out as many times as its count.
Call choose(0, 0). The kept combinations are already in lexicographic order.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Backtrack in ascending order and prune

Intuition

Build each combination one value at a time, the way you would write it down: in ascending order. The start index enforces that order. After you place nums[i], the next value may be nums[i] again, because a candidate can repeat, or any later value, but never an earlier one. So the call that placed index i loops only from i onward. Each combination has exactly one ascending order, so it has exactly one path in the tree, and a duplicate such as [3, 2, 3] is never built.

Here is the whole tree for sorted [2, 3, 6] and target 8. The root has 8 left and tries 2, 3 and 6. Under 2 you have 6 left. Under 2, 2 you have 4 left, and 2, 2, 2 leaves 2, which one more 2 turns into the answer [2, 2, 2, 2]; 2, 2, 3 leaves 1 and dies. Under 2, 3 you have 3 left and may try only 3 and 6, and the 3 gives [2, 3, 3]. Under 2, 6 nothing is left: [2, 6]. Under 3 you may try only 3 and 6, and 3, 3 leaves 2, which neither fills. Under 6 you have 2 left and may try only 6. Twelve calls in all, against the 30 leaves of the first approach.

Sorting turns a dead end into an early stop. When nums[i] is larger than what is left, every later value is larger too, so you leave the loop with break instead of testing the rest. In the tree above, the node 2, 2, 3 with 1 left looks at 3, sees that it does not fit, and never looks at 6. The search only visits prefixes whose sum is still at most target, which is why the large tests that sink the first approach take a few thousand calls here.

The output order comes from the same walk. At every level the loop tries smaller values first, and every combination is written in ascending order. Two answers first differ at the level where their paths split, and the path with the smaller value there was explored first, so the answers arrive in lexicographic order. A combination can never be a prefix of another, since the values are positive and both reach the same total.

Algorithm

Sort the candidates in ascending order.
Write backtrack(start, remaining) that shares one list path. If remaining is 0, save a copy of path.
Otherwise loop i from start to the end. If nums[i] > remaining, break: every later value is bigger.
Append nums[i], call backtrack(i, remaining-nums[i]) with i, not i + 1, so the value can repeat, then remove it.
Call backtrack(0, target) and return the saved combinations, already in lexicographic order.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Pitfalls and edge cases

Most wrong answers come from how the search is ordered, not from the arithmetic.

Looping over every candidate at every level, instead of from the current index, builds [2, 3, 3], [3, 2, 3] and [3, 3, 2] as three answers. Sorting each answer and removing duplicates afterwards gives the right list but does exponentially more work.
Recursing with i + 1 instead of i lets each value appear only once, so [2, 2, 2, 2] goes missing.
Saving path itself instead of a copy: every saved answer is then the same list, which the backtracking has emptied by the end.
Using break on candidates you did not sort. With [6, 2, 3] and 2 left, the loop stops at 6 and never tries the 2.
Returning the combinations in the order the unsorted input suggests. The expected list is in lexicographic order, which the sorted search gives without an extra sort.
In Lua and R, arrays start at 1, so the first call starts at index 1 and the loop runs up to the length of the array.

Frequently asked questions4

What is the time complexity of Combination Sum?

The backtracking search is exponential. With n candidates, target t and smallest candidate m, a combination holds at most t/m values and each step has at most n choices, which bounds the work by O(n^(t/m)). Pruning on sorted candidates keeps the real number of calls far below that, because the search only visits prefixes whose sum is still at most t. The extra space is O(t/m) for the current path and the call stack, plus the output.

Why do you recurse with i and not i + 1 in Combination Sum?

Recursing with i lets the next value be the same candidate again, which is how a value gets used more than once. Recursing with i + 1 moves past it, which turns the problem into the variant where each candidate is used at most once. The other half of the rule matters as much: never going back to an index before i keeps every combination in ascending order and stops duplicates.

How do you avoid duplicate combinations without a set?

Generate every combination in one fixed order, ascending. The start index enforces it: after placing nums[i], the search only looks at nums[i] and later values. Every combination then has exactly one path in the search tree, so it is produced once, and no set or final deduplication is needed.

Can Combination Sum be solved with dynamic programming?

Yes. Keep, for every total from 0 to target, the list of combinations that reach it, and add one candidate at a time so the values in each list stay ascending, the same idea as counting the ways to make change. It never explores a dead end twice, but it stores every partial combination for every total, which costs far more memory than backtracking, and the final list may need sorting. Since the output itself can be exponential, backtracking is the usual answer.

Python

def combinationSum(candidates, target):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

candidates = [6, 2, 3]
target = 8

Expected

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]