#39

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Combination Sum

Find all unique combinations of numbers from a distinct array that sum to a target using controlled backtracking search.

array backtracking

Problem Statement

Given a list of distinct integers called candidates and a target integer, return all unique combinations where chosen numbers sum to the target. Each candidate may be used multiple times, and the order of combinations does not matter.

Two combinations are considered unique if at least one number appears a different number of times. The total number of valid combinations is guaranteed to be less than 150, ensuring the backtracking search completes efficiently under these constraints.

Examples

Example 1

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

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

2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2

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

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

Example details omitted.

Example 3

Input: candidates = [2], target = 1

Output: []

Example details omitted.

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Solution Approach

Sort Candidates and Initialize Backtracking

Sort the array to allow early termination when the cumulative sum exceeds the target. Begin backtracking with an empty path and the starting index at 0, ensuring each recursive call considers candidates at or after the current index.

Recursive Backtracking with Pruning

For each candidate, add it to the current path and recursively attempt to reach the target. If the path sum exceeds the target, immediately backtrack. Reuse candidates by allowing recursive calls to continue from the current index instead of incrementing it.

Collect and Return Valid Combinations

Whenever the cumulative sum equals the target, add a copy of the current path to the results. Continue exploring other combinations by backtracking, removing the last candidate, and trying the next option in the loop.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of valid combinations and recursion depth, which is influenced by the target value and candidate magnitudes. Space complexity is driven by recursion stack depth and storage of all valid combinations.

What Interviewers Usually Probe

Checks if you handle repeated use of candidates correctly.
Observes whether you prune branches when the cumulative sum exceeds the target.
Evaluates if you maintain the uniqueness of combinations without extra structures.

Common Pitfalls or Variants

Common pitfalls

Failing to prune when the path sum exceeds the target, causing unnecessary recursion.
Modifying the path in place without restoring it, leading to incorrect combinations.
Incrementing the index too early and missing valid repeated candidate combinations.

Follow-up variants

Limit each candidate to be used at most once, changing the backtracking logic to increment the index after use.
Return combinations in non-descending order and remove duplicates, requiring sorting and skipping duplicates.
Find combinations whose sum is closest to a target without exceeding it, needing additional tracking of best sums.

FAQ

Can a candidate number be used multiple times in Combination Sum?

Yes, each number can be chosen unlimited times, which is why backtracking needs to continue from the current index rather than moving forward.

How does pruning improve the backtracking performance?

Pruning stops recursion once the path sum exceeds the target, preventing exploration of invalid combinations and reducing time complexity.

Are the combinations in any specific order?

No, the problem allows returning combinations in any order as long as each combination itself reflects the correct counts of candidates.

What is the key failure mode in this problem?

A common failure is incorrectly handling repeated candidates or failing to backtrack properly, leading to missing or duplicated combinations.

How is the backtracking pattern applied in Combination Sum?

Backtracking explores each candidate recursively, reuses candidates as needed, and prunes paths exceeding the target to efficiently enumerate all valid combinations.

terminal

Solution

Solution 1: Sorting + Pruning + Backtracking

We can first sort the array to facilitate pruning.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                ans.append(t[:])
                return
            if s < candidates[i]:
                return
            for j in range(i, len(candidates)):
                t.append(candidates[j])
                dfs(j, s - candidates[j])
                t.pop()

        candidates.sort()
        t = []
        ans = []
        dfs(0, target)
        return ans

Solution 2: Sorting + Pruning + Backtracking(Another Form)

We can also change the implementation logic of the function $dfs(i, s)$ to another form. In the function $dfs(i, s)$, we first check whether $s$ is $0$. If it is, we add the current search path $t$ to the answer $ans$, and then return. If $i \geq n$ or $s \lt candidates[i]$, the path is invalid, so we return directly. Otherwise, we consider two situations, one is not selecting the element of the current index, that is, recursively calling the function $dfs(i + 1, s)$, and the other is selecting the element of the current index, that is, recursively calling the function $dfs(i, s - candidates[i])$.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                ans.append(t[:])
                return
            if s < candidates[i]:
                return
            for j in range(i, len(candidates)):
                t.append(candidates[j])
                dfs(j, s - candidates[j])
                t.pop()

        candidates.sort()
        t = []
        ans = []
        dfs(0, target)
        return ans

Continue Practicing

#40 combination sum ii #37 sudoku solver #46 permutations