LeetCode 39 - Combination Sum

This Medium problem asks for every combination of candidates whose sum equals the target. A candidate may be used more than once, but combinations that differ only in order must appear once. I used backtracking to build each combination while carrying its remaining sum and the earliest candidate index available to the next recursive call.

---

Problem link and explanation

• Problem: 39. Combination Sum
• Summary: Given an array of distinct positive integers and a target, return every unique combination whose sum equals the target.

For this input:

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

the valid combinations are:

[2, 2, 3]
[7]

The value 2 can be selected repeatedly. However, [2, 2, 3], [2, 3, 2], and [3, 2, 2] represent the same combination, so the search must allow repeated values without generating every ordering of them.

---

Approach

Carry the current path and remaining sum

The recursive function keeps the selected values in path and subtracts each selection from remain.

path   = values selected so far
remain = target minus the sum of path

When remain reaches zero, the current path is a complete answer.

if remain == 0:
    answer.append(path[:])
    return

Use a start index to prevent duplicate orderings

Each recursive call loops from start_index to the end of the candidates. After selecting candidates[i], it passes i, rather than i + 1, to the next call.

self.backtrack(candidates, remain - candidates[i], i, path, answer)

Passing i allows the current candidate to be selected again. At the same time, the search never returns to an earlier index, so it can generate [2, 2, 3] but not the reordered versions [2, 3, 2] or [3, 2, 2].

Sort before pruning

I sorted the candidates before starting the search. Once a candidate is greater than the remaining sum, every candidate after it is also too large, so the loop can stop.

candidates.sort()

if remain < candidates[i]:
    break

Sorting does not remove duplicate combinations by itself. The start index controls ordering; sorting makes this pruning condition valid.

Choose, recurse, and restore

For each candidate, the function appends the value, explores that branch, and then removes it before trying the next candidate.

path.append(candidates[i])
self.backtrack(candidates, remain - candidates[i], i, path, answer)
path.pop()

The final pop restores the shared path to the state it had before the recursive call.

---

Troubleshooting

My first implementation appended path directly when it found a valid combination.

if remain == 0:
    answer.append(path)
    return

After the search finished, the combinations that had been found were empty. The entries in answer and the working path all referred to the same list object. As backtracking continued to call path.pop(), it also changed the list referenced by every saved result.

The fix was to save a shallow copy containing the values at that moment.

answer.append(path[:])

Calling copy() is an equivalent and more explicit option here. Since the path contains integers, either form creates the independent list needed for the result.

answer.append(path.copy())

---

Complexity analysis

• Time complexity: O(N^(T/M))

  • N is the number of candidates, T is the target, and M is the smallest candidate. A path can reach a depth of at most T / M, and each level may consider up to N candidates. Pruning reduces the number of branches explored for a particular input.

• Space complexity: O(T/M)

  • The recursion stack and working path can both reach a depth of T / M. The returned combinations occupy additional output space.

---

Implementation code

from typing import List

class Solution:
    def backtrack(
        self,
        candidates: List[int],
        remain: int,
        start_index: int,
        path: List[int],
        answer: List[List[int]],
    ) -> None:
        if remain == 0:
            answer.append(path[:])
            return

        for i in range(start_index, len(candidates)):
            if remain < candidates[i]:
                break

            path.append(candidates[i])
            self.backtrack(candidates, remain - candidates[i], i, path, answer)
            path.pop()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        answer = []

        candidates.sort()
        self.backtrack(candidates, target, 0, path, answer)

        return answer

---

Summary and reflection

Backtracking fits this problem because every valid combination must be explored. The search still needs clear boundaries: start_index fixes the selection order and prevents duplicate permutations, while sorting allows branches to stop as soon as the remaining sum is smaller than the next candidate.

The shared path also has to be copied when a result is recorded. Backtracking deliberately mutates one list with append and pop, so storing that same object would allow later recursive work to overwrite an answer that was already found.