Combination Sum

Q: 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 with at most n choices each: O(n^(t/m)) . The extra space is O(t/m) for the path and the call stack, plus the output.

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, so each candidate could be used at most once.

Q: Can Combination Sum be solved with dynamic programming?

Yes. For every total from 0 to target , keep the combinations that reach it, adding one candidate at a time so each list stays ascending. It never explores a dead end twice, but it stores every partial combination for every total, which costs far more memory. Since the output itself can be exponential, backtracking is the usual answer.

MediumBacktracking

+10

You get a list candidates of different positive integers and a positive integer target. Find every combination of candidates that adds up to exactly target, using each candidate as many times as you like. [2, 3, 3] and [3, 2, 3] are the same combination.

Return each combination in ascending order, and the combinations in lexicographic order: at the first position where two combinations differ, the one with the smaller value 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, 2 + 3 + 3 and 2 + 6 all make 8, ordered by their second value. Without a 2 only 3s and 6s are left, and their sums are multiples 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, and [3, 3, 5] comes first because its second value, 3, is smaller than 4. No mix of 4s and 5s alone makes 11.

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

The trap is building the same combination twice: 2, 3, 3 and 3, 2, 3 are one answer. Build each combination in ascending order, so it has exactly one path, and sort the candidates so a branch stops as soon as the next value is larger than what is left.

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: [2, 3, 3] is one 2, two 3s and no 6. Try every count for each sorted candidate, from target / c down to 0, keeping the choices that total exactly target. Each combination has one list of counts, so none is found twice. Larger counts first gives lexicographic order: where two answers first differ, the one with more copies of a value still holds that value while the other holds a bigger one.

For [2, 3, 6] and target 8 there are 5 × 3 × 2 = 30 leaves for 3 answers. Each candidate above target / 2 doubles the leaves, so 40 such candidates mean 2^40, about 10^12.

Algorithm

Sort the candidates and keep one count per value.
In choose(i, total), try each count k from target / nums[i] down to 0 and call choose(i + 1, total + k × nums[i]).
Once every value has a count, keep the combination if total equals target and write it out from the counts.
Call choose(0, 0).

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

After you place nums[i], the next value may be nums[i] again or any later value, never an earlier one. A combination has exactly one ascending order, so it has exactly one path, and [3, 2, 3] is never built.

For sorted [2, 3, 6] and target 8, the paths 2, 2, 2, 2 and 2, 3, 3 and 2, 6 reach 8. The path 2, 2, 3 leaves 1 and stops without looking at 6, and 3, 3 leaves 2, which no value fits. That is 12 calls against the 30 leaves of counting.

At every level the loop tries smaller values first, so the answers arrive in lexicographic order. No answer is a prefix of another, since the values are positive and both reach the same total.

Algorithm

Sort the candidates.
In backtrack(start, remaining), save a copy of the shared path when remaining is 0.
Otherwise loop i from start. If nums[i] > remaining, break: every later value is bigger.
Append nums[i], call backtrack(i, remaining - nums[i]), then remove it.
Call backtrack(0, target) and return the saved combinations.

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

Looping over every candidate at every level, instead of from the current index. [2, 3, 3], [3, 2, 3] and [3, 3, 2] then come out as three answers.
Recursing with i + 1 instead of i. Each value can then appear once, so [2, 2, 2, 2] goes missing.
Saving path itself instead of a copy. Every saved answer is then the same list, which 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.

Frequently asked questions3

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 with at most n choices each: O(n^(t/m)). The extra space is O(t/m) for the 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, so each candidate could be used at most once.

Can Combination Sum be solved with dynamic programming?

Yes. For every total from 0 to target, keep the combinations that reach it, adding one candidate at a time so each list stays ascending. It never explores a dead end twice, but it stores every partial combination for every total, which costs far more memory. Since the output itself can be exponential, backtracking is the usual answer.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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