Combination Sum

• Difficulty: Medium
• Topics: Array, Backtracking
• Link: https://leetcode.com/problems/combination-sum/

Problem Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
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 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

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

Solution

Combination Sum: Comprehensive Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Technical Version

Given an array candidates containing $n$ distinct positive integers $(c_1, c_2, ..., c_n)$ and a positive integer target $T$, enumerate all unique multisets (combinations with repetition) of elements from candidates such that the sum of the multiset equals $T$. Formally, find all vectors $(x_1, x_2, ..., x_n) \in \mathbb{Z}_{\geq0}^n$ satisfying:

$$\sum_{i=1}^{n} x_i \cdot c_i = T$$

where two solutions are considered identical if their corresponding multisets are equal (i.e., the frequency distribution of chosen elements is identical). The enumeration must avoid permutations of the same multiset.

Beginner Version

You have a list of different numbers. You’re allowed to pick any number from the list as many times as you want. Your goal is to find all the different groups of numbers (where order doesn’t matter) that add up exactly to a target number. For example, if your list is [2,3,6,7] and the target is 7, you could use [2,2,3] (using 2 twice and 3 once) or just [7]. Note that [2,3,2] is considered the same as [2,2,3] because we only care about which numbers and how many times, not the order you pick them.

Mathematical Version

Let $C = \{c_1, c_2, ..., c_k\}$ be a set of distinct positive integers. For a given positive integer $T$, find all solutions to the linear Diophantine equation with non-negative coefficients:

$$\sum_{i=1}^{k} a_i c_i = T, \quad a_i \in \mathbb{Z}_{\geq0}$$

The solution space corresponds to the integer lattice points in the $k$-dimensional non-negative orthant bounded by $a_i \leq \lfloor T/c_i \rfloor$. Two solutions $(a_1, ..., a_k)$ and $(b_1, ..., b_k)$ are considered distinct if and only if $\exists i: a_i \neq b_i$.

Constraint Analysis

1. 1 <= candidates.length <= 30

   • Limitation: The branching factor in recursive solutions is bounded by 30. However, since we can reuse elements, the depth of recursion could theoretically be up to $T/\min(candidates)$.
   • Hidden implication: With $n \leq 30$, a brute-force approach checking all combinations (including different multiplicities) would be $O((T/\min)^n)$, which is astronomically large for worst-case values. This forces us to use smarter pruning.

2. 2 <= candidates[i] <= 40

   • Limitation: All numbers are at least 2, ensuring that any combination has at most $\lfloor T/2 \rfloor$ elements (for $T \leq 40$, max 20 elements).
   • Hidden edge case: Since all candidates are $\geq 2$, when $T = 1$, no solution exists regardless of candidates (handled in Example 3).
   • Optimization opportunity: We can sort candidates and break early when a candidate exceeds the remaining target.

3. All elements of candidates are distinct

   • Implication: No need to handle duplicate values in input, which simplifies duplicate combination avoidance.
   • Hidden benefit: In backtracking, we don’t need special logic to skip identical values at the same depth.

4. 1 <= target <= 40

   • Key insight: The search space is small. The worst-case number of combinations is bounded (<150 per problem statement).
   • Algorithm selection: Exponential-time algorithms (backtracking) are acceptable; dynamic programming with table size $O(T)$ is efficient.
   • Edge case: When $T$ is smaller than all candidates, output is empty list.

5. Combination count < 150 (implied from test generation)

   • Critical insight: The output size is manageable, so we don’t need to worry about exponential blow-up in output storage.
   • Design implication: We can afford to store all combinations in memory without concern for memory limits.

2. Intuition Scaffolding

Three Analogies

1. Real-World Metaphor: Coin Change Problem Imagine you’re a cashier with a limited set of coin denominations (candidates). You need to give exact change equal to the target amount. You can use each coin type as many times as you want. Your task is to list all distinct sets of coins that sum to the target. For example, to make 7 cents with coins [2,3,6,7], you could use {2,2,3} or {7}. The order of coins doesn’t matter—{2,3,2} is the same as {2,2,3}.

2. Gaming Analogy: Crafting System In a resource-gathering game, you have basic materials with different point values (candidates). To craft an item requiring $T$ points, you can combine materials in any quantity. Each distinct bundle of materials that sums to $T$ unlocks a different crafting recipe. The game tracks only the counts of each material, not the order you add them to the crafting table.

3. Mathematical Analogy: Integer Partition with Restricted Parts This is the problem of partitioning the integer $T$ into parts drawn only from the set $C$, where each part can be used multiple times. Unlike standard integer partitions, we don’t consider all integers, only those in $C$. Additionally, we consider different arrangements of the same multiset as identical (order doesn’t matter).

Common Pitfalls (5+ Examples)

1. Generating Permutations as Separate Combinations

   • Wrong approach: Recursing without restrictions, allowing any candidate at each step.
   • Why it fails: Produces [2,2,3], [2,3,2], [3,2,2] as different combinations.
   • Visualization: The search tree has redundant subtrees representing the same multiset.

2. Missing Pruning Opportunities

   • Wrong approach: Continuing recursion even when current sum exceeds target.
   • Why it fails: Wastes time on impossible paths. For large $T$, this leads to exponential blow-up.

3. Incorrect Duplicate Handling via Sorting Results

   • Wrong approach: Generate all permutations, sort each combination, then use a set to filter.
   • Why it fails: The number of permutations can be huge ($k!$ for combinations with $k$ distinct elements). For [1,2,…,30] with $T=40$, this is computationally infeasible.

4. Overlooking the Unlimited Use Condition

   • Wrong approach: Treating the problem as “each candidate can be used at most once” (like a knapsack).
   • Why it fails: Misses valid combinations like [2,2,2,2] for target 8 with candidates [2,3,5].

5. Inefficient Candidate Ordering

   • Wrong approach: Not sorting candidates, then failing to prune when a candidate exceeds remaining target.
   • Why it fails: For unsorted [7,2,3,6], we might check 7 first for target 5, fail, then check 2, etc. But if sorted, we’d check 2,3,6, then stop at 7.

6. Infinite Recursion Risk

   • Wrong approach: No progression mechanism in recursion, always considering the same candidate.
   • Why it fails: For candidate [2] and target 3, recursion might try 2, then 2 again (sum=4>3), backtrack, try 2 again… actually, with proper base cases this stops, but without a way to stop considering the same candidate, it could loop if we don’t reduce the target.

3. Approach Encyclopedia

Approach 1: Brute Force Recursion (Naive)

Core Idea: Generate all possible sequences by trying every candidate at every step, then filter duplicates.

def combinationSumNaive(candidates, target):
    result_set = set()
    
    def dfs(current_sum, current_path):
        if current_sum == target:
            # Sort to make combination canonical
            sorted_path = tuple(sorted(current_path))
            result_set.add(sorted_path)
            return
        if current_sum > target:
            return
        
        for num in candidates:
            dfs(current_sum + num, current_path + [num])
    
    dfs(0, [])
    return [list(comb) for comb in result_set]

Complexity Proof:

• Time: Let $m = \lfloor T/\min(C) \rfloor$ be the maximum combination length. At each of $m$ positions, we have $n$ choices, giving $O(n^m)$ recursive calls. For worst-case $n=30$, $T=40$, $\min(C)=2$, $m=20$, this is $30^{20} \approx 3.5 \times 10^{29}$ operations.
• Space: $O(m)$ for recursion depth, plus $O(C \cdot m)$ for storing results, where $C$ is the number of combinations.

Visualization:

Level 0: []
Level 1: [2], [3], [6], [7]  (for candidates=[2,3,6,7])
Level 2: [2,2], [2,3], [2,6], [2,7], [3,2], [3,3], ...
Level 3: [2,2,2], [2,2,3], [2,2,6], ...

Note the explosion of redundant paths.

Approach 2: Backtracking with Ordering (Optimal)

Core Idea: Sort candidates, then at each step only consider candidates from the current index onward. This ensures combinations are generated in non-decreasing order, eliminating permutations.

def combinationSumBacktrack(candidates, target):
    candidates.sort()  # Critical: enables pruning and duplicate prevention
    result = []
    
    def backtrack(start_idx, remaining, path):
        # Base case: exact sum reached
        if remaining == 0:
            result.append(path[:])  # Copy the path
            return
        
        # Try each candidate from start_idx onward
        for i in range(start_idx, len(candidates)):
            num = candidates[i]
            # Prune if num exceeds remaining (since sorted)
            if num > remaining:
                break  # Not continue, because all later nums are larger
            
            # Choose num
            path.append(num)
            # Recurse with same i (allow reuse)
            backtrack(i, remaining - num, path)
            # Unchoose (backtrack)
            path.pop()
    
    backtrack(0, target, [])
    return result

Complexity Proof:

• Time: Let $K$ be the number of valid combinations (bounded by 150). Each combination of length $L$ requires $L$ recursive calls to build. Thus worst-case time is $O(K \cdot L_{max})$ where $L_{max} \leq T/\min(C) \leq 20$. This gives $O(150 \cdot 20) = O(3000)$ operations, ignoring constant factors.
• Space: $O(L_{max})$ for recursion stack and current path, plus $O(K \cdot L_{avg})$ for storing results.

Visualization for candidates=[2,3,6,7], target=7:

Start: backtrack(0, 7, [])
  i=0, num=2 ≤7: path=[2], backtrack(0,5,[2])
    i=0, num=2 ≤5: path=[2,2], backtrack(0,3,[2,2])
      i=0, num=2 ≤3: path=[2,2,2], backtrack(0,1,[2,2,2])
        i=0, num=2 >1: break
      i=1, num=3 ≤3: path=[2,2,3], backtrack(1,0,[2,2,3]) ✓ Add [2,2,3]
        remaining=0, add to result
      i=2, num=6 >3: break
    i=1, num=3 ≤5: path=[2,3], backtrack(1,2,[2,3])
      i=1, num=3 >2: break
    i=2, num=6 >5: break
  i=1, num=3 ≤7: path=[3], backtrack(1,4,[3])
    i=1, num=3 ≤4: path=[3,3], backtrack(1,1,[3,3])
      i=1, num=3 >1: break
    i=2, num=6 >4: break
  i=2, num=6 ≤7: path=[6], backtrack(2,1,[6])
    i=2, num=6 >1: break
  i=3, num=7 ≤7: path=[7], backtrack(3,0,[7]) ✓ Add [7]

Approach 3: Dynamic Programming (Bottom-Up)

Core Idea: Build a DP table where dp[i] contains all combinations summing to i. For each candidate, update combinations for all sums from candidate to target.

def combinationSumDP(candidates, target):
    # dp[i] will store list of combinations summing to i
    dp = [[] for _ in range(target + 1)]
    dp[0] = [[]]  # Base: one way to make sum 0 (empty combination)
    
    for num in sorted(candidates):
        for t in range(num, target + 1):
            for comb in dp[t - num]:
                dp[t].append(comb + [num])
    
    return dp[target]

Complexity Proof:

• Time: Outer loop: $n$ candidates. Middle loop: $T$ iterations. Inner loop: iterates over combinations in dp[t-num]. In worst case, each dp[i] could contain many combinations, but total combinations across all dp[i] is bounded by the total number of valid combinations (less than 150 for final target, but intermediate sums could have more). Theoretical worst-case: $O(n \cdot T \cdot C_{max})$ where $C_{max}$ is max combinations for any sum.
• Space: $O(T \cdot C_{avg})$ to store all combinations for all sums up to target.

Visualization for candidates=[2,3,6,7], target=7:

Initialize: dp[0] = [[]]

Process num=2:
  t=2: dp[2] = dp[0] + [2] = [[2]]
  t=3: dp[3] = dp[1] + [2] = [] (dp[1] empty)
  t=4: dp[4] = dp[2] + [2] = [[2,2]]
  t=5: dp[5] = dp[3] + [2] = []
  t=6: dp[6] = dp[4] + [2] = [[2,2,2]]
  t=7: dp[7] = dp[5] + [2] = []

Process num=3:
  t=3: dp[3] += dp[0] + [3] = [[3]]
  t=4: dp[4] += dp[1] + [3] = [[2,2]] (no change)
  t=5: dp[5] += dp[2] + [3] = [[2,3]]
  t=6: dp[6] += dp[3] + [3] = [[2,2,2], [3,3]]
  t=7: dp[7] += dp[4] + [3] = [[2,2,3]]

Process num=6:
  t=6: dp[6] += dp[0] + [6] = [[2,2,2], [3,3], [6]]
  t=7: dp[7] += dp[1] + [6] = [[2,2,3]] (no change)

Process num=7:
  t=7: dp[7] += dp[0] + [7] = [[2,2,3], [7]]

Result: dp[7] = [[2,2,3], [7]]

Approach 4: Recursion with Early Pruning (Alternative Backtracking)

Core Idea: Use recursion that at each call decides how many times to use the current candidate before moving to the next.

def combinationSumRecursive(candidates, target):
    candidates.sort()
    result = []
    
    def dfs(index, remaining, path):
        if remaining == 0:
            result.append(path[:])
            return
        if index == len(candidates):
            return
        
        # Try using candidates[index] multiple times
        num = candidates[index]
        max_count = remaining // num
        
        # Try 0 to max_count copies of num
        for count in range(max_count + 1):
            new_remaining = remaining - count * num
            if new_remaining < 0:
                break
            # Add count copies of num
            path.extend([num] * count)
            dfs(index + 1, new_remaining, path)
            # Remove them
            for _ in range(count):
                path.pop()
    
    dfs(0, target, [])
    return result

Complexity: Similar to Approach 2.

4. Code Deep Dive

Optimal Solution (Backtracking with Ordering)

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # Sort candidates: enables pruning and ensures non-decreasing combinations
        # Why? (1) We can break when candidate > remaining, (2) Prevents permutations
        candidates.sort()
        
        result = []  # Store all valid combinations
        
        def backtrack(start: int, remaining: int, path: List[int]):
            """
            start: index from which we can choose candidates (avoids going backwards)
            remaining: the amount left to sum to target
            path: current combination being built
            """
            # Base case 1: exact match found
            if remaining == 0:
                # Make a copy since path will be modified by backtracking
                result.append(path.copy())
                return
            
            # Base case 2: overshoot - handled in loop by pruning
            
            # Iterate through candidates starting from 'start'
            for i in range(start, len(candidates)):
                num = candidates[i]
                
                # Prune: if current number exceeds remaining, stop
                # Since candidates are sorted, all subsequent numbers will also exceed
                if num > remaining:
                    break  # Not 'continue' - breaking ends the loop entirely
                
                # Choose: add num to current path
                path.append(num)
                
                # Explore: recurse with same 'i' (allow reuse)
                # Key insight: passing 'i' instead of 'i+1' allows unlimited reuse
                backtrack(i, remaining - num, path)
                
                # Unchoose: backtrack by removing last element
                path.pop()
        
        # Start backtracking from index 0 with full target and empty path
        backtrack(0, target, [])
        return result

Line-by-Line Annotations

Line 4: candidates.sort() - Sorts input in ascending order. Critical for:

• Pruning: When num > remaining, we can break because all subsequent numbers are larger.
• Duplicate prevention: By only moving forward in the candidate list (start index), we ensure combinations are generated in non-decreasing order.

Line 6: result = [] - Stores final combinations. Using a list since order doesn’t matter per problem statement.

Lines 8-35: backtrack function - The recursive engine.

Line 13: if remaining == 0: - Base case: exact sum achieved. Add current path to results.

Line 14: result.append(path.copy()) - Must copy because path is mutable and will be modified during backtracking. Without copy, all entries in result would reference the same list.

Line 19: for i in range(start, len(candidates)): - Iterates from start to end. start ensures we never consider candidates before the current index, preventing permutations like [2,3] and [3,2].

Line 22: if num > remaining: break - Pruning step. Because candidates are sorted, once we encounter a number too large, all subsequent numbers are also too large.

Line 26: path.append(num) - Choose the current candidate.

Line 30: backtrack(i, remaining - num, path) - Recurse with:

• Same index i: allows reusing the current candidate unlimited times.
• Reduced remaining: subtracts the chosen value.
• Same path: will be modified in recursion.

Line 33: path.pop() - Backtrack: remove the last chosen candidate to try the next candidate in the loop.

Line 38: backtrack(0, target, []) - Initial call: start from first candidate with full target and empty combination.

Edge Case Handling

Example 1: candidates = [2,3,6,7], target = 7

• Sorted already: [2,3,6,7]
• Recursion builds [2,2,3] and [7] as shown in visualization.
• Line 22 prunes when trying 6 with remaining 1.

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

• Sorted already: [2,3,5]
• Finds [2,2,2,2] (using four 2’s), [2,3,3], [3,5].
• Demonstrates unlimited reuse and pruning when 5 > remaining in certain branches.

Example 3: candidates = [2], target = 1

• Single candidate 2 > target 1, so loop breaks immediately at line 22.
• Returns empty list [].

Edge Case: All candidates > target

• For candidates = [10,20,30], target = 5
• Sorting gives [10,20,30], first candidate 10 > 5, loop breaks, returns [].

Edge Case: Exact match with single candidate

• candidates = [5], target = 5
• Path [5] added when remaining == 0.

5. Complexity War Room

Hardware-Aware Analysis

Memory Footprint:

• Input size: candidates list of up to 30 integers (4 bytes each) = 120 bytes.
• Recursion stack: Maximum depth = $T/\min(C) \leq 40/2 = 20$ frames. Each frame stores: start (4 bytes), remaining (4 bytes), path reference (8 bytes), loop variable (4 bytes) ≈ 20 bytes per frame. Total stack: 20 × 20 = 400 bytes.
• Current path: Maximum 20 integers = 80 bytes.
• Output storage: <150 combinations, average length ≤ 10 elements, each 4 bytes = 150 × 10 × 4 = 6KB.
• Total: <10KB, easily fits in L1 cache (32-64KB typical).

CPU Considerations:

• Branch prediction: The if num > remaining: break creates predictable branching patterns when candidates are sorted.
• Cache locality: Sequential access to sorted candidates array benefits from prefetching.

Scalability Analysis:

• If constraints were increased (e.g., target up to 1000), backtracking would still work but recursion depth increases.
• For extremely large targets, dynamic programming might use too much memory (storing all combinations for all intermediate sums).

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability	Best For
Brute Force (Naive)	$O(n^{T/\min})$	$O(T/\min)$ recursion	High	❌ Fails large cases	Educational only
Backtracking + Ordering	$O(K \cdot L)$ where $K$ = #combos, $L$ = avg length	$O(T/\min)$ recursion + output	Very High	✅ Most expected	General use, interview standard
Dynamic Programming (Bottom-Up)	$O(n \cdot T \cdot C_{avg})$	$O(T \cdot C_{total})$ storage	Medium	✅ Acceptable alternative	When all combinations needed for all sums
Recursion with Count Loop	$O(K \cdot L)$	$O(T/\min)$ recursion + output	High	✅ Good alternative	When thinking in terms of multiplicities

Legend:

• $n$ = number of candidates (≤30)
• $T$ = target (≤40)
• $K$ = number of valid combinations (<150)
• $L$ = average combination length
• $C_{avg}$ = average combinations per sum in DP

Interview Viability Notes:

• Backtracking with ordering is the gold standard: demonstrates understanding of recursion, pruning, and duplicate avoidance.
• Always mention sorting first: shows algorithmic thinking about optimization.
• Discuss pruning strategy: “Since candidates are sorted, we can break when candidate exceeds remaining target.”

6. Pro Mode Extras

Variants Section

1. Combination Sum II (LeetCode 40)

   • Change: Each candidate can be used at most once, and candidates may contain duplicates.
   • Solution modification: Sort candidates, backtrack with i+1 (no reuse), and skip duplicates with if i > start and candidates[i] == candidates[i-1]: continue.

2. Combination Sum III (LeetCode 216)

   • Change: Find all combinations of k numbers from 1-9 that sum to n, each used at most once.
   • Solution modification: Backtrack from 1 to 9, track count of numbers used, and only add when count == k and sum == n.

3. Combination Sum IV (LeetCode 377)

   • Change: Count the number of combinations (order matters - actually permutations).
   • Solution: Dynamic programming: dp[i] = sum(dp[i-num] for num in candidates if num <= i).

4. Limited Use Variant

   • Change: Each candidate has a maximum usage count limit[i].
   • Solution modification: In backtracking, track usage count per candidate, or use the count-loop approach with min(limit[i], remaining//num).

5. Negative Numbers Allowed

   • Change: Candidates may include negative numbers.
   • Complication: Can’t prune when num > remaining (since adding negative could reduce sum). Also, risk of infinite loops if sum cycles.
   • Solution: Must bound recursion depth or use DP with careful state representation.

Interview Cheat Sheet

Step-by-Step Thought Process to Verbalize:

1. “First, I’ll sort the candidates. This lets me prune branches where the current candidate exceeds the remaining target.”
2. “I’ll use backtracking/DFS to explore combinations, maintaining a start index to avoid generating permutations of the same set.”
3. “At each step, I can choose to use the current candidate (and stay at the same index for potential reuse) or move to the next candidate.”
4. “I’ll prune when the remaining target becomes negative or when the current candidate is too large.”
5. “Time complexity is bounded by the number of valid combinations (<150), space is O(T/min) for recursion.”

Common Follow-up Questions:

• Q: “What if candidates contained duplicates?” A: “Sort first, then in backtracking, skip duplicates with if i > start and candidates[i] == candidates[i-1]: continue.”
• Q: “How would you handle very large targets (e.g., 10^6)?” A: “Backtracking might be too slow. Could use dynamic programming to count combinations, but enumerating all might be impossible due to exponential output size. Would discuss trade-offs.”
• Q: “What if we wanted the combination with fewest elements?” A: “Could modify backtracking to track depth and keep the shortest valid combination, or use BFS level-order search.”

Key Optimization Points to Mention:

1. Sorting enables O(1) pruning decision.
2. The start index technique eliminates duplicate combinations without needing a set.
3. Passing remaining as parameter avoids recalculating sum from path.
4. Using path.copy() when adding to results prevents reference issues.

Red Flags to Avoid:

• Don’t suggest generating all permutations then filtering.
• Don’t forget to sort candidates.
• Don’t use i+1 in the recursive call unless you want to disallow reuse.
• Don’t forget to make a copy of the path when adding to results.

Testing Strategy:

1. Small case: candidates=[2], target=1 → []
2. Single candidate match: [2], target=2 → [[2]]
3. All candidates > target: [10,20], target=5 → []
4. Duplicate combinations check: [2,3], target=5 should give only [[2,3]], not [[2,3],[3,2]]
5. Large combination: [2], target=40 → single combination of twenty 2’s.