LeetCode 39 - Combination Sum

LeetCode Problem 39

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

Problem Understanding

This problem asks us to generate every possible unique combination of numbers from the given candidates array such that the sum of the chosen numbers equals target.

There are several important details in the problem statement:

• Every number in candidates is distinct.
• Each number can be used an unlimited number of times.
• The output should contain only unique combinations.
• The order inside a combination does not matter.

For example, if candidates = [2,3,6,7] and target = 7, then [2,2,3] is valid because:

• 2 + 2 + 3 = 7
• 2 may be reused multiple times

However, [3,2,2] is not considered a different answer because it contains the same numbers with the same frequencies.

The input consists of:

• An integer array candidates
• A target integer target

The expected output is a list of lists, where each inner list represents one valid combination whose sum equals the target.

The constraints are relatively small:

• candidates.length <= 30
• target <= 40

These constraints strongly suggest that an exponential or backtracking solution is acceptable. Since the target is small and the number of valid combinations is guaranteed to stay below 150, exhaustive search with pruning is practical.

Several edge cases are important:

• No valid combination exists, such as candidates = [2] and target = 1
• A candidate equals the target directly
• One candidate can be reused many times
• Multiple paths may generate the same combination if ordering is not controlled carefully

The main challenge is generating all valid combinations while avoiding duplicates.

Approaches

Brute Force Approach

A naive brute force strategy would try every possible sequence of candidate selections and check whether the sum equals the target.

For every recursive step, we could choose any candidate again and continue building combinations until:

• The sum becomes exactly the target
• The sum exceeds the target

This method eventually finds all valid combinations because it explores every possible construction.

However, this approach has a major problem. It generates duplicate permutations of the same combination.

For example:

• [2,2,3]
• [2,3,2]
• [3,2,2]

All represent the same logical combination, but brute force treats them as separate paths.

To remove duplicates, we would need additional data structures such as sorting and hash sets, which increases overhead significantly.

The search space also grows exponentially because every recursive call can branch into multiple additional calls.

Optimal Backtracking Approach

The key insight is that combinations do not care about ordering.

If we ensure that recursive exploration only moves forward through the candidate list, we naturally avoid duplicate permutations.

For example:

• We allow [2,2,3]
• We never allow going backward to generate [3,2,2]

This transforms the problem into a classic backtracking search.

At each recursive step:

• Choose the current candidate
• Stay at the same index if we want to reuse it
• Move forward when skipping it

This guarantees uniqueness while still exploring every valid combination.

Because the target is small, pruning is extremely effective:

• If the current sum exceeds the target, stop immediately
• If the remaining target becomes zero, record the current combination

This makes backtracking the ideal solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^target) to O(n^target)	O(target)	Explores all possible sequences, generates duplicates
Optimal Backtracking	O(N^(T/M))	O(target)	Efficient pruning and duplicate avoidance

Where:

• N = number of candidates
• T = target
• M = smallest candidate value

Algorithm Walkthrough

Optimal Backtracking Algorithm

1. Initialize an empty result list that will store all valid combinations.
2. Create a recursive backtracking function that accepts:

• The current index in candidates
• The remaining target value
• The current combination being built

3. If the remaining target becomes 0, the current combination is valid.

• Copy the current combination into the result list.
• Return immediately because no more numbers are needed.

4. If the remaining target becomes negative, stop exploring this path.

• This branch can never produce a valid combination.

5. Iterate through candidates starting from the current index.

• Starting from the current index prevents generating duplicate permutations.
• This guarantees combinations remain in non-decreasing order.

6. Add the current candidate to the combination.
7. Recursively call the backtracking function:

• Pass the same index again because the candidate may be reused unlimited times.
• Subtract the candidate value from the remaining target.

8. After recursion finishes, remove the last element from the combination.

• This is the "backtracking" step.
• It restores the previous state before exploring the next possibility.

9. Continue exploring all remaining candidates.

Why it works

The algorithm systematically explores every valid combination while enforcing a fixed ordering constraint. Since recursion only moves forward through the candidate list, duplicate permutations can never occur. Every valid combination is eventually explored because each candidate can either be included repeatedly or skipped. Pruning ensures invalid paths terminate early.

Python Solution

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        current_combination = []

        def backtrack(start_index: int, remaining: int) -> None:
            if remaining == 0:
                result.append(current_combination[:])
                return

            if remaining < 0:
                return

            for index in range(start_index, len(candidates)):
                candidate = candidates[index]

                current_combination.append(candidate)

                backtrack(index, remaining - candidate)

                current_combination.pop()

        backtrack(0, target)

        return result

The implementation begins by initializing two lists:

• result stores all valid combinations
• current_combination tracks the active recursive path

The nested backtrack function performs the recursive exploration.

The parameter start_index ensures combinations are generated in a consistent order. This is the mechanism that prevents duplicates.

The parameter remaining tracks how much value is still needed to reach the target.

When remaining == 0, a valid combination has been constructed. A copy of the current combination is added to the result list.

When remaining < 0, the current path is impossible and recursion stops immediately.

The loop iterates starting from start_index, not from 0. This is extremely important because it prevents revisiting earlier candidates and generating duplicate permutations.

The recursive call uses backtrack(index, remaining - candidate) instead of index + 1 because the same number may be reused multiple times.

After recursion completes, the last element is removed using pop(). This restores the previous recursive state before exploring another branch.

Go Solution

func combinationSum(candidates []int, target int) [][]int {
    var result [][]int
    var currentCombination []int

    var backtrack func(startIndex int, remaining int)

    backtrack = func(startIndex int, remaining int) {
        if remaining == 0 {
            combinationCopy := make([]int, len(currentCombination))
            copy(combinationCopy, currentCombination)

            result = append(result, combinationCopy)
            return
        }

        if remaining < 0 {
            return
        }

        for index := startIndex; index < len(candidates); index++ {
            candidate := candidates[index]

            currentCombination = append(currentCombination, candidate)

            backtrack(index, remaining-candidate)

            currentCombination = currentCombination[:len(currentCombination)-1]
        }
    }

    backtrack(0, target)

    return result
}

The Go implementation follows the same recursive structure as the Python solution.

One important Go-specific detail is copying slices before storing them in the result. Slices are references to underlying arrays, so directly appending currentCombination would cause future modifications to affect stored results.

To avoid this, the implementation creates combinationCopy and copies the slice contents before appending.

Go also uses slice re-slicing for backtracking:

currentCombination = currentCombination[:len(currentCombination)-1]

Unlike Python, Go does not have automatic list copying with slicing syntax like [:], so explicit copy() usage is necessary.

Worked Examples

Example 1

Input:

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

Recursive Exploration

Current Combination	Remaining Target	Action
[]	7	Start recursion
[2]	5	Choose 2 again
[2,2]	3	Choose 2 again
[2,2,2]	1	Choose 2 again
[2,2,2,2]	-1	Invalid, backtrack
[2,2,3]	0	Valid combination
[2,3]	2	Continue searching
[2,3,3]	-1	Invalid
[3]	4	Continue
[3,3]	1	Continue
[6]	1	Continue
[7]	0	Valid combination

Final output:

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

Example 2

Input:

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

Recursive Exploration

Current Combination	Remaining Target	Result
[2,2,2,2]	0	Valid
[2,3,3]	0	Valid
[3,5]	0	Valid

Final output:

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

Example 3

Input:

candidates = [2]
target = 1

Recursive Exploration

Current Combination	Remaining Target	Result
[2]	-1	Invalid

No valid combination exists.

Final output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N^(T/M))	Recursive branching based on candidate choices
Space	O(target)	Maximum recursion depth occurs when repeatedly choosing smallest candidate

The runtime is exponential because the algorithm explores many possible combinations recursively. The branching factor depends on the number of candidates, while the recursion depth depends on how many times the smallest number can fit into the target.

The space complexity comes primarily from the recursion stack and the current combination being constructed. In the worst case, the recursion depth can reach target / smallest_candidate.

Test Cases

solution = Solution()

# Example 1
assert sorted(solution.combinationSum([2,3,6,7], 7)) == sorted([[2,2,3],[7]])

# Example 2
assert sorted(solution.combinationSum([2,3,5], 8)) == sorted([
    [2,2,2,2],
    [2,3,3],
    [3,5]
])

# Example 3
assert solution.combinationSum([2], 1) == []

# Single candidate equals target
assert solution.combinationSum([7], 7) == [[7]]

# Multiple reuse of same element
assert solution.combinationSum([1], 3) == [[1,1,1]]

# No possible combination
assert solution.combinationSum([5,10], 3) == []

# Multiple valid combinations
assert sorted(solution.combinationSum([2,4,6], 8)) == sorted([
    [2,2,2,2],
    [2,2,4],
    [2,6],
    [4,4]
])

# Larger target with many paths
assert sorted(solution.combinationSum([2,3,5], 10)) == sorted([
    [2,2,2,2,2],
    [2,2,3,3],
    [2,3,5],
    [5,5]
])

# Candidate larger than target
assert solution.combinationSum([9], 7) == []

# Target reachable in only one way
assert solution.combinationSum([4], 8) == [[4,4]]

Test	Why
[2,3,6,7], 7	Basic example with multiple solutions
[2,3,5], 8	Multiple branching paths
[2], 1	No valid solution
[7], 7	Candidate equals target directly
[1], 3	Unlimited reuse validation
[5,10], 3	All candidates exceed target
[2,4,6], 8	Multiple combination lengths
[2,3,5], 10	Larger recursive search space
[9], 7	Immediate pruning case
[4], 8	Single repeated candidate

Edge Cases

One important edge case occurs when no valid combination exists. For example, candidates = [2] and target = 1. A naive implementation might recurse infinitely or incorrectly return partial combinations. This solution handles the case safely because recursion immediately stops whenever the remaining target becomes negative.

Another important edge case is when a single candidate equals the target directly. For example, candidates = [7] and target = 7. Some implementations accidentally skip direct matches due to incorrect recursion order or premature pruning. This implementation correctly detects the solution when the remaining target reaches zero.

A third critical edge case involves repeated reuse of a single number. For example, candidates = [1] and target = 5. Since numbers may be reused unlimited times, the recursion must allow revisiting the same index. This implementation achieves that by recursively calling backtrack(index, remaining - candidate) instead of advancing to the next index.

Another subtle edge case is duplicate permutation generation. Without careful ordering constraints, the algorithm could produce both [2,3,2] and [3,2,2]. The implementation avoids this entirely by only exploring candidates from the current index forward, guaranteeing combinations remain ordered consistently.