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

Item	Meaning
Input	candidates and target
Output	A list of valid combinations
Candidate reuse	Each candidate can be used unlimited times
Candidate values	Distinct integers
Combination order	[2,2,3] and [2,3,2] count as the same combination

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:

Rule	Effect
Recurse with i	Allows unlimited reuse of the same candidate
Never go back to smaller indices	Prevents duplicate permutations

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:

Variable	Meaning
start	First candidate index allowed in this call
remain	Remaining sum needed to reach target
path	Current partial combination
ans	All valid combinations found

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

Metric	Value	Why
Time	Exponential	The search may explore many partial combinations
Space	O(target / min(candidates)) excluding output	This is the maximum recursion depth

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:

Test	Why
[2,3,6,7], target 7	Basic reuse case
[2,3,5], target 8	Multiple valid combinations
[2], target 1	No solution
[1], target 2	Reuse same candidate
Unsorted candidates	Confirms sorting works
All candidates too large	Returns empty list