MediumBacktrackingRecursionArray

Combination Sum

1 approach, code in every language

You are given a list of distinct positive integers called candidates and a positive whole number target. Find every unique group of numbers drawn from candidates whose elements add up exactly to target. A single candidate value may be reused as many times as you like within one group.

Two groups are considered the same if they contain the identical multiset of numbers regardless of order, so each distinct combination should be reported only once. Return all the combinations in any order.

Example 1

Input: candidates = [2, 3, 6, 7], target = 7

Output: [[2, 2, 3], [7]]

Two plus two plus three equals seven, and seven by itself also reaches the target.

Example 2

Input: candidates = [2, 3, 5], target = 8

Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Each listed group sums to eight and no group repeats another as a multiset.

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All values in candidates are distinct
1 <= target <= 500

Sorted backtracking with reuse

Sort the candidates, then explore combinations by always continuing from the current index so values can repeat, pruning branches once a candidate exceeds the remaining amount.

Loading animation…

Intuition

Sorting lets us stop scanning as soon as a candidate is larger than what remains, because everything after it is even larger. To avoid producing the same multiset in different orders, each recursive call only considers candidates from the current index onward. Passing the same index into the next call permits reuse of a value, while advancing the index in the loop guarantees we never revisit an earlier smaller value and create a duplicate ordering.

Algorithm walkthrough

1Sort candidates in ascending order so we can prune early.
2Track the remaining amount and the path of chosen numbers.
3When the remaining amount hits zero, save a copy of the current path.
4Loop from the current start index; if a candidate exceeds the remaining amount, break because later ones are bigger.
5Choose a candidate, recurse with the same index to allow reuse, then remove it to backtrack.

Implementation

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        candidates.sort()

        def backtrack(start: int, remaining: int, path: list[int]) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                path.append(candidates[i])
                backtrack(i, remaining - candidates[i], path)
                path.pop()

        backtrack(0, target, [])
        return result

Time

O(2^t) in the worst case

Space

O(t)

Here t relates to target divided by the smallest candidate, which bounds recursion depth and result length.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Exact Postage Mixes is our own problem on the technique behind Combination Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free