LeetCode 39: Combination Sum

Problem Restatement

We are given an array of distinct integers candidates and an integer target.

We need to return all unique combinations of numbers from candidates whose sum equals target.

Each candidate number may be chosen unlimited times.

Two combinations are considered different only when the frequency of at least one chosen number is different. The result may be returned in any order. The test cases guarantee fewer than 150 valid combinations.

Input and Output

Function shape:

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    ...

Examples

Example 1:

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

Valid combinations:

[2, 2, 3]
[7]

Return:

[[2, 2, 3], [7]]

Example 2:

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

Valid combinations:

[2, 2, 2, 2]
[2, 3, 3]
[3, 5]

Return:

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Example 3:

candidates = [2]
target = 1

No combination can sum to 1.

Return:

[]

First Thought: Try Every Possible List

A direct idea is to try building every possible list of numbers.

At each step, choose any candidate and add it to the current list.

Stop when the sum reaches or exceeds target.

This finds valid answers, but it creates duplicates.

For example, with:

candidates = [2, 3]
target = 5

we may generate both:

[2, 3]
[3, 2]

These are the same combination because they use one 2 and one 3.

We need a way to generate each frequency pattern only once.

Key Insight

Force combinations to be built in non-decreasing candidate-index order.

At each recursive call, we pass a start index.

The next chosen candidate must come from:

candidates[start:]

If we choose candidates[i], the recursive call starts again at i, not i + 1, because the same number may be reused.

That gives us two important properties:

For example, after choosing 3, we never go back and choose 2.

So [3, 2] is never generated if [2, 3] already represents that combination.

Algorithm

Sort candidates.

Then use backtracking with:

Recursive function:

backtrack(start, remain)

Base cases:

1. If remain == 0, copy path into ans.
2. If remain < 0, stop.

For each index i from start to the end:

1. Let value = candidates[i].
2. If value > remain, break because the array is sorted.
3. Append value to path.
4. Recurse with backtrack(i, remain - value).
5. Pop value from path.

Correctness

The algorithm only appends a combination when remain == 0. Since remain starts as target and every chosen value is subtracted from it, remain == 0 means the chosen values sum exactly to target.

The algorithm never creates invalid combinations in the answer. If a path exceeds the target, then remain becomes negative or a sorted pruning condition stops that branch before it can be recorded.

Every valid combination can be represented in non-decreasing candidate-index order. The algorithm explores exactly that kind of order because each recursive call only allows candidates from the current index onward. Since choosing index i recurses with i, the same candidate can appear multiple times.

The algorithm also avoids duplicates. Any duplicate ordering such as [3, 2] would require going from a larger candidate index back to a smaller one. The start rule forbids that. Therefore, each unique frequency pattern is generated once.

So the algorithm returns all and only valid unique combinations.

Complexity

The output itself can contain many lists. The problem guarantees fewer than 150 valid combinations for the given input.

Implementation

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

        ans = []
        path = []

        def backtrack(start: int, remain: int) -> None:
            if remain == 0:
                ans.append(path.copy())
                return

            for i in range(start, len(candidates)):
                value = candidates[i]

                if value > remain:
                    break

                path.append(value)
                backtrack(i, remain - value)
                path.pop()

        backtrack(0, target)
        return ans

Code Explanation

Sort the candidates first:

candidates.sort()

Sorting lets us stop early when a candidate is already larger than the remaining sum.

The answer list stores complete combinations:

ans = []

The path list stores the current partial combination:

path = []

The recursive function receives the first candidate index still allowed:

def backtrack(start: int, remain: int) -> None:

When remain == 0, the current path is complete:

if remain == 0:
    ans.append(path.copy())
    return

We must append a copy because path will keep changing during backtracking.

Now try each allowed candidate:

for i in range(start, len(candidates)):

If the value is too large, all later values are also too large because the array is sorted:

if value > remain:
    break

Choose the value:

path.append(value)

Recurse with i, not i + 1, because the same value may be chosen again:

backtrack(i, remain - value)

Undo the choice before trying the next value:

path.pop()

Finally, start the search:

backtrack(0, target)

Testing

def normalize(result: list[list[int]]) -> list[list[int]]:
    return sorted(sorted(row) for row in result)

def check(candidates: list[int], target: int, expected: list[list[int]]) -> None:
    actual = Solution().combinationSum(candidates, target)
    assert normalize(actual) == normalize(expected), (candidates, target, actual, expected)

def run_tests():
    check([2, 3, 6, 7], 7, [[2, 2, 3], [7]])
    check([2, 3, 5], 8, [[2, 2, 2, 2], [2, 3, 3], [3, 5]])
    check([2], 1, [])
    check([1], 2, [[1, 1]])
    check([7, 3, 2], 7, [[2, 2, 3], [7]])
    check([5, 10], 3, [])

    print("all tests passed")

run_tests()

Test meaning: