Data Structures & AlgorithmsCommon Backtracking Patterns

Common Backtracking Patterns

LevelIntermediate

Duration90 mins

TopicCommon Backtracking Patterns

2 / 4

Combination Sum Problems

The Numeric Combination Challenge

Imagine you're a cashier with an infinite supply of certain coin denominations, and a customer needs exact change. Or you're a project manager who needs to allocate a fixed budget across different cost options. Or you're designing a game where players must combine power-ups to reach an exact energy level. All of these scenarios share a common structure: finding combinations of numbers that sum to a target.

The Combination Sum problem family represents one of the most important and frequently encountered backtracking patterns. These problems ask us to find all ways to combine elements from a set to achieve a target sum, with varying constraints on how elements can be reused. Mastering this pattern equips you to handle a vast array of real-world optimization and search problems.

What You Will Learn

By the end of this page, you will master the core Combination Sum problem and its major variants, understand the subtle differences between allowing duplicate use vs. single use of elements, learn techniques to avoid generating duplicate combinations, and develop intuition for when and how to optimize these solutions.

The Combination Sum Problem Family

The Combination Sum family consists of several closely related problems, each with slightly different constraints. Understanding the differences is crucial for applying the right solution.

Combination Sum I (LeetCode 39):

Given an array of distinct integers and a target
Find all unique combinations that sum to the target
Each number may be used unlimited times
Order doesn't matter (combinations, not permutations)

Combination Sum II (LeetCode 40):

Given an array that may contain duplicates and a target
Find all unique combinations that sum to the target
Each element may be used at most once
Must handle duplicate elements to avoid duplicate combinations

Combination Sum III (LeetCode 216):

Find combinations of k numbers from 1-9
Each number used at most once
Combinations must sum to target n

Combination Sum IV (LeetCode 377):

Count the number of permutations (order matters)
Actually a dynamic programming problem, not backtracking

Combination Sum Variants Comparison
Variant	Duplicates in Input?	Element Reuse	Key Challenge
Combination Sum I	No (distinct)	Unlimited	Allow same element repeatedly in path
Combination Sum II	Yes (may have)	At most once	Skip duplicate elements to avoid duplicate results
Combination Sum III	No (fixed 1-9)	At most once	Additional constraint on combination size
Combination Sum IV	No (distinct)	Unlimited	Count permutations (use DP instead)

Combinations vs. Permutations

Combination Sum I-III generate combinations where order doesn't matter: [2,2,3] and [3,2,2] are the same combination. Combination Sum IV counts permutations where order matters: [2,2,3] and [3,2,2] are different. This fundamental distinction determines whether backtracking or DP is the right approach.

Combination Sum I: Unlimited Element Use

Let's start with the foundational variant where elements can be reused unlimited times.

Problem Statement:

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. The same number may be chosen an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3], [7]]
Explanation: 2+2+3=7 and 7=7 are the only combinations

The Backtracking Insight:

The key insight is that at each step, we have multiple choices:

Include the current candidate (and consider it again since reuse is allowed)
Move to the next candidate (never use this one again in this path)

This creates a decision tree where each path represents a combination. We prune branches where the running sum exceeds the target.

combination_sum_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    """
    Find all combinations that sum to target, with unlimited reuse.
    
    Time Complexity: O(N^(T/M)) where N = len(candidates), T = target, M = min(candidates)
    Space Complexity: O(T/M) for recursion depth
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(path[:])  # Append a copy of the current path
            return
        
        # Base case: exceeded target, prune this branch
        if remaining < 0:
            return
        
        # Explore candidates starting from 'start' index
        # This ensures we don't generate permutations (e.g., [2,3] and [3,2])
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            # Optimization: if current candidate > remaining, skip
            # (Works only if candidates are sorted)
            if candidate > remaining:
                break  # All subsequent candidates are larger too
            
            # CHOOSE: Add candidate to the path
            path.append(candidate)
            
            # EXPLORE: Recurse with 'i' (not i+1) to allow reuse
            backtrack(i, remaining - candidate, path)
            
            # UNCHOOSE: Remove candidate from path (backtrack)
            path.pop()
    
    # Sort to enable early termination optimization
    candidates.sort()
    backtrack(0, target, [])
    return result
 
 
# Example usage
print(combinationSum([2, 3, 6, 7], 7))
# Output: [[2, 2, 3], [7]]
 
print(combinationSum([2, 3, 5], 8))
# Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

The 'start' Parameter Trick

Notice we pass 'i' (not 'i+1') when recursing. This is the key difference enabling reuse—we can pick the same element again. But we still use 'start' to prevent generating reverse orderings. Starting from index 0 each time would give us both [2,3] and [3,2], which represent the same combination.

Combination Sum II: Handling Duplicates

Combination Sum II introduces a significant complication: the input array may contain duplicate values, but each element can only be used once, and we must not return duplicate combinations.

Problem Statement:

Given a collection of candidate numbers candidates (which may contain duplicates) and a target number target, find all unique combinations where the candidate numbers sum to target. Each number may be used only once in the combination.

Example:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

The Duplicate Challenge:

Consider candidates = [1,1,2] with target 3. If we naively apply backtracking:

Pick first 1, then 2 → [1,2] ✓
Pick second 1, then 2 → [1,2] (duplicate!)

We'd generate [1,2] twice because there are two 1s in the input. The challenge is avoiding this without missing valid combinations like [1,1] that legitimately use both 1s.

combination_sum_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    """
    Find all unique combinations that sum to target, each element used once.
    
    Key insight: Sort the array, then skip duplicates at the same recursion level.
    
    Time Complexity: O(2^N) where N = len(candidates)
    Space Complexity: O(N) for recursion depth and path
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(path[:])
            return
        
        # Base case: exceeded target
        if remaining < 0:
            return
        
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            # CRUCIAL: Skip duplicates at the same recursion level
            # If candidates[i] == candidates[i-1], we've already explored
            # all combinations starting with this value at this position
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            
            # Optimization: early termination (sorted array)
            if candidate > remaining:
                break
            
            # CHOOSE
            path.append(candidate)
            
            # EXPLORE with i+1 (each element used at most once)
            backtrack(i + 1, remaining - candidate, path)
            
            # UNCHOOSE
            path.pop()
    
    # CRITICAL: Sort to group duplicates together
    candidates.sort()
    backtrack(0, target, [])
    return result
 
 
# Example usage
print(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
# Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
 
print(combinationSum2([2, 5, 2, 1, 2], 5))
# Output: [[1, 2, 2], [5]]

Understanding the Duplicate-Skipping Logic:

The line if i > start and candidates[i] == candidates[i-1]: continue is subtle but crucial. Let's understand it deeply:

candidates = [1, 1, 2] (sorted), target = 3

First call: start=0
  i=0, pick first 1 → recurse with start=1
    i=1, pick second 1 → recurse with start=2
      i=2, pick 2 → sum=4 > target, backtrack
    i=2, pick 2 → sum=3 = target ✓ [1,2]
  i=1, candidates[1]==candidates[0], but i>start, SKIP!
     ↑ This prevents picking the "second 1" as the first element
       because we already explored "first 1" in that position
  i=2, pick 2 → recurse with start=3
    No more elements, backtrack

The key insight: at the same recursion level (same start), choosing the first occurrence of a value explores all combinations using that value. Choosing subsequent duplicates would regenerate the same combinations.

The i > start Condition

The condition 'i > start' is crucial. Without it, we'd skip valid uses of consecutive duplicates. When i == start, we're at a new recursion level—we haven't tried anything at this level yet, so we shouldn't skip. We only skip when i > start, meaning we've already processed at least one candidate at this level.

Visualizing the Search Tree

Understanding backtracking is enormously helped by visualizing the search tree. Let's trace through a complete example.

Example: Combination Sum I

candidates = [2, 3], target = 6

                          []
                     /          \
                  [2]            [3]
                /     \            \
            [2,2]    [2,3]         [3,3]
           /    \       \              X (9>6)
      [2,2,2]  [2,2,3]  [2,3,3]
         ✓        X       X
       (=6)     (7>6)   (8>6)

Reading the tree:

Each node shows the current path
Edges represent choosing the next candidate
✓ marks valid combinations (sum = target)
X marks pruned branches (sum > target)
We always move right-or-same (never left) to avoid duplicate combinations

Key observations:

From [2], we can choose 2 again (going to [2,2]) or move to 3 (going to [2,3])
From [3], we can only choose 3 (going to [3,3]), not 2, because 2 comes before 3
We never generate [3,2,..] because that would duplicate combinations from [2,3,..]

Converting Mermaid diagram...

Example: Combination Sum II with Duplicates

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

                              []
                    /          |          \
                [1]           [1]          [2]
               ↓              ↓ SKIP!       ↓
              /   \                      (no valid)
          [1,1]   [1,2]
            ↓       ↓
         (=2)     (=3)✓
          ↓
      [1,1,2]
         ↓
       (=4)X

Notice that the second [1] at the root level is SKIPPED because:

i=1 > start=0 (we've already processed something at this level)
candidates[1] == candidates[0] (duplicate value)

This ensures we don't generate duplicate combinations while still allowing [1,1] which uses both 1s at different recursion levels.

Combination Sum III: Fixed-Size Combinations

Combination Sum III adds an additional constraint: we must use exactly k numbers from the range 1-9, and each can be used at most once.

Problem Statement:

Find all valid combinations of k numbers that sum up to n such that:

Only numbers 1 through 9 are used
Each number is used at most once

Example:

Input: k=3, n=7
Output: [[1,2,4]]
Explanation: 1+2+4=7, using exactly 3 numbers

Additional Constraint Handling:

This variant requires tracking two constraints simultaneously:

The running sum must not exceed target
The combination length must not exceed k

We can use both constraints for pruning, making the search more efficient.

combination_sum_3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def combinationSum3(k: int, n: int) -> list[list[int]]:
    """
    Find k numbers from 1-9 (each used once) that sum to n.
    
    Time Complexity: O(C(9,k) * k) ≈ O(9! / (k! * (9-k)!))
    Space Complexity: O(k) for recursion depth
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if len(path) == k:
            if remaining == 0:
                result.append(path[:])
            return  # Don't continue—we have exactly k elements
        
        # Pruning: if we've exceeded the sum or can't pick enough numbers
        if remaining <= 0:
            return
        
        # Additional pruning: not enough numbers left to fill k slots
        if 9 - start + 1 < k - len(path):
            return
        
        for num in range(start, 10):  # 1 to 9
            # Optimization: if num > remaining, no point continuing
            if num > remaining:
                break
            
            # CHOOSE
            path.append(num)
            
            # EXPLORE (num+1 because each number used at most once)
            backtrack(num + 1, remaining - num, path)
            
            # UNCHOOSE
            path.pop()
    
    backtrack(1, n, [])  # Start from 1
    return result
 
 
# Examples
print(combinationSum3(3, 7))   # [[1, 2, 4]]
print(combinationSum3(3, 9))   # [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
print(combinationSum3(2, 18))  # []  (max is 9+8=17)

Multi-Constraint Pruning

With multiple constraints, apply all of them for pruning. In Combination Sum III, we prune when: (1) sum exceeds target, (2) path length reaches k, (3) not enough numbers remain. Each additional constraint dramatically reduces the search space.

Complexity Analysis Across Variants

Understanding the complexity of Combination Sum variants helps you predict performance and choose appropriate optimizations.

Combination Sum I Complexity:

With unlimited reuse, the worst case is filling the target entirely with the smallest element. If candidates = [1,...], target = T, we might pick 1 repeatedly T times, with branching factor N at each level.

Time: O(N^(T/M)) where N = |candidates|, T = target, M = min(candidates)
Space: O(T/M) for recursion depth

Combination Sum II Complexity:

Each element used at most once means maximum recursion depth is N (pick all elements).

Time: O(2^N) — each element is either included or excluded
Space: O(N) for recursion depth and path

Combination Sum III Complexity:

We're choosing k elements from 9, with various pruning.

Time: O(C(9,k) × k) = O(9! / (k! × (9-k)!) × k)
Space: O(k) for recursion depth

For k=4 (the maximum useful value since 1+2+...+9=45), this is at most C(9,4)×4 = 126×4 = 504 operations.

Time Complexity Comparison
Variant	Time Complexity	Practical Bound	Notes
Combination Sum I	O(N^(T/M))	Can be large for small M	Sorting + pruning crucial
Combination Sum II	O(2^N)	Manageable for N ≤ 30	Duplicate skipping essential
Combination Sum III	O(C(9,k) × k)	At most ~500 ops	Fixed input range limits search

Why These Problems Are Solvable

Despite exponential worst-case complexity, these problems are practical because: (1) Input sizes are constrained (LeetCode limits N to ~30, target to ~500), (2) Sorting enables aggressive pruning, (3) Sum constraints eliminate most branches early. The theoretical exponential bound rarely manifests in practice.

Common Pitfalls and Edge Cases

The Combination Sum problems have several subtle gotchas that catch even experienced programmers. Let's catalog them.

Pitfall 1: Forgetting to Copy the Path

# WRONG
result.append(path)  # Appends a reference!

# All entries in result point to the same list
# which gets modified as backtracking continues

# CORRECT
result.append(path[:])  # or list(path) or path.copy()

The path list is reused across recursive calls. Appending the reference means all results share the same list, which ends up empty after all backtracking completes.

Pitfall 2: Off-by-One in Duplicate Skipping

# WRONG
if candidates[i] == candidates[i-1]:  # Missing i > start check!
    continue

# This skips ALL duplicates, even valid ones at different levels

# CORRECT
if i > start and candidates[i] == candidates[i-1]:
    continue

Pitfall 3: Using i+1 vs i for Recursion

Combination Sum I (unlimited reuse): pass i to allow reusing same element
Combination Sum II (single use): pass i+1 to move past used element

Mixing these up gives incorrect results silently—tests might pass for some cases.

Common Mistakes

•Appending path reference instead of copy
•Forgetting to sort before duplicate skipping
•Wrong recursion index (i vs i+1)
•Missing i > start condition
•Not handling empty input or zero target

Edge Cases to Test

•Target equals a single candidate
•Target is 0 (empty combination valid?)
•All candidates larger than target
•Single candidate that divides target
•All identical candidates (e.g., [1,1,1,1])

The Zero Target Trap

What if target = 0? Depending on problem constraints, either the empty combination [] is valid, or 0 is not a valid input. Check problem constraints carefully. For most LeetCode variants, target ≥ 1, but in real interviews, clarify this edge case.

Summary: Mastering Combination Sum

The Combination Sum family represents a fundamental backtracking pattern that appears throughout algorithmic problem-solving. Let's consolidate our learning:

Key Takeaways

•The start parameter prevents duplicate combinations — By always choosing from index ≥ start, we ensure each combination is generated exactly once in a canonical order.
•Reuse control: i vs i+1 — Pass 'i' to allow unlimited reuse, pass 'i+1' to enforce single use. This one-character difference changes the entire problem semantics.
•Duplicate handling requires sorting + the i > start check — Sort to group duplicates, then skip when we've already explored a duplicate at the current recursion level.
•Sorting enables early termination — Once candidate > remaining, all subsequent candidates are larger and can be skipped.
•Always copy the path when recording results — The path list is reused; appending a reference causes all results to share the same (eventually empty) list.
•Multi-constraint problems apply all constraints for pruning — Combination Sum III uses both sum and count constraints to dramatically reduce search space.

What's next:

With the Combination Sum pattern mastered, we'll explore Palindrome Partitioning—a problem that combines string processing with backtracking to find all ways to split a string into palindromic substrings. This pattern introduces the concept of generating partitions and demonstrates backtracking on string structure.

Page Complete

You now have deep mastery of the Combination Sum problem family. These patterns—managing element reuse, handling duplicates, and controlling combination order—appear in countless variations. Practice implementing all three variants from scratch to solidify your understanding.

2 / 4

Loading learning content...

Data Structures & AlgorithmsCommon Backtracking Patterns

Common Backtracking Patterns

LevelIntermediate

Duration90 mins

TopicCommon Backtracking Patterns

2 / 4

Combination Sum Problems

The Numeric Combination Challenge

What You Will Learn

The Combination Sum Problem Family

The Combination Sum family consists of several closely related problems, each with slightly different constraints. Understanding the differences is crucial for applying the right solution.

Combination Sum I (LeetCode 39):

Given an array of distinct integers and a target
Find all unique combinations that sum to the target
Each number may be used unlimited times
Order doesn't matter (combinations, not permutations)

Combination Sum II (LeetCode 40):

Given an array that may contain duplicates and a target
Find all unique combinations that sum to the target
Each element may be used at most once
Must handle duplicate elements to avoid duplicate combinations

Combination Sum III (LeetCode 216):

Find combinations of k numbers from 1-9
Each number used at most once
Combinations must sum to target n

Combination Sum IV (LeetCode 377):

Count the number of permutations (order matters)
Actually a dynamic programming problem, not backtracking

Combination Sum Variants Comparison
Variant	Duplicates in Input?	Element Reuse	Key Challenge
Combination Sum I	No (distinct)	Unlimited	Allow same element repeatedly in path
Combination Sum II	Yes (may have)	At most once	Skip duplicate elements to avoid duplicate results
Combination Sum III	No (fixed 1-9)	At most once	Additional constraint on combination size
Combination Sum IV	No (distinct)	Unlimited	Count permutations (use DP instead)

Combinations vs. Permutations

Combination Sum I: Unlimited Element Use

Let's start with the foundational variant where elements can be reused unlimited times.

Problem Statement:

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3], [7]]
Explanation: 2+2+3=7 and 7=7 are the only combinations

The Backtracking Insight:

The key insight is that at each step, we have multiple choices:

Include the current candidate (and consider it again since reuse is allowed)
Move to the next candidate (never use this one again in this path)

This creates a decision tree where each path represents a combination. We prune branches where the running sum exceeds the target.

combination_sum_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    """
    Find all combinations that sum to target, with unlimited reuse.
    
    Time Complexity: O(N^(T/M)) where N = len(candidates), T = target, M = min(candidates)
    Space Complexity: O(T/M) for recursion depth
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(path[:])  # Append a copy of the current path
            return
        
        # Base case: exceeded target, prune this branch
        if remaining < 0:
            return
        
        # Explore candidates starting from 'start' index
        # This ensures we don't generate permutations (e.g., [2,3] and [3,2])
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            # Optimization: if current candidate > remaining, skip
            # (Works only if candidates are sorted)
            if candidate > remaining:
                break  # All subsequent candidates are larger too
            
            # CHOOSE: Add candidate to the path
            path.append(candidate)
            
            # EXPLORE: Recurse with 'i' (not i+1) to allow reuse
            backtrack(i, remaining - candidate, path)
            
            # UNCHOOSE: Remove candidate from path (backtrack)
            path.pop()
    
    # Sort to enable early termination optimization
    candidates.sort()
    backtrack(0, target, [])
    return result
 
 
# Example usage
print(combinationSum([2, 3, 6, 7], 7))
# Output: [[2, 2, 3], [7]]
 
print(combinationSum([2, 3, 5], 8))
# Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

The 'start' Parameter Trick

Combination Sum II: Handling Duplicates

Combination Sum II introduces a significant complication: the input array may contain duplicate values, but each element can only be used once, and we must not return duplicate combinations.

Problem Statement:

Example:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

The Duplicate Challenge:

Consider candidates = [1,1,2] with target 3. If we naively apply backtracking:

Pick first 1, then 2 → [1,2] ✓
Pick second 1, then 2 → [1,2] (duplicate!)

We'd generate [1,2] twice because there are two 1s in the input. The challenge is avoiding this without missing valid combinations like [1,1] that legitimately use both 1s.

combination_sum_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    """
    Find all unique combinations that sum to target, each element used once.
    
    Key insight: Sort the array, then skip duplicates at the same recursion level.
    
    Time Complexity: O(2^N) where N = len(candidates)
    Space Complexity: O(N) for recursion depth and path
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(path[:])
            return
        
        # Base case: exceeded target
        if remaining < 0:
            return
        
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            
            # CRUCIAL: Skip duplicates at the same recursion level
            # If candidates[i] == candidates[i-1], we've already explored
            # all combinations starting with this value at this position
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            
            # Optimization: early termination (sorted array)
            if candidate > remaining:
                break
            
            # CHOOSE
            path.append(candidate)
            
            # EXPLORE with i+1 (each element used at most once)
            backtrack(i + 1, remaining - candidate, path)
            
            # UNCHOOSE
            path.pop()
    
    # CRITICAL: Sort to group duplicates together
    candidates.sort()
    backtrack(0, target, [])
    return result
 
 
# Example usage
print(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
# Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
 
print(combinationSum2([2, 5, 2, 1, 2], 5))
# Output: [[1, 2, 2], [5]]

Understanding the Duplicate-Skipping Logic:

The line if i > start and candidates[i] == candidates[i-1]: continue is subtle but crucial. Let's understand it deeply:

candidates = [1, 1, 2] (sorted), target = 3

First call: start=0
  i=0, pick first 1 → recurse with start=1
    i=1, pick second 1 → recurse with start=2
      i=2, pick 2 → sum=4 > target, backtrack
    i=2, pick 2 → sum=3 = target ✓ [1,2]
  i=1, candidates[1]==candidates[0], but i>start, SKIP!
     ↑ This prevents picking the "second 1" as the first element
       because we already explored "first 1" in that position
  i=2, pick 2 → recurse with start=3
    No more elements, backtrack

The i > start Condition

Visualizing the Search Tree

Understanding backtracking is enormously helped by visualizing the search tree. Let's trace through a complete example.

Example: Combination Sum I

candidates = [2, 3], target = 6

                          []
                     /          \
                  [2]            [3]
                /     \            \
            [2,2]    [2,3]         [3,3]
           /    \       \              X (9>6)
      [2,2,2]  [2,2,3]  [2,3,3]
         ✓        X       X
       (=6)     (7>6)   (8>6)

Reading the tree:

Each node shows the current path
Edges represent choosing the next candidate
✓ marks valid combinations (sum = target)
X marks pruned branches (sum > target)
We always move right-or-same (never left) to avoid duplicate combinations

Key observations:

From [2], we can choose 2 again (going to [2,2]) or move to 3 (going to [2,3])
From [3], we can only choose 3 (going to [3,3]), not 2, because 2 comes before 3
We never generate [3,2,..] because that would duplicate combinations from [2,3,..]

Converting Mermaid diagram...

Example: Combination Sum II with Duplicates

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

                              []
                    /          |          \
                [1]           [1]          [2]
               ↓              ↓ SKIP!       ↓
              /   \                      (no valid)
          [1,1]   [1,2]
            ↓       ↓
         (=2)     (=3)✓
          ↓
      [1,1,2]
         ↓
       (=4)X

Notice that the second [1] at the root level is SKIPPED because:

i=1 > start=0 (we've already processed something at this level)
candidates[1] == candidates[0] (duplicate value)

This ensures we don't generate duplicate combinations while still allowing [1,1] which uses both 1s at different recursion levels.

Combination Sum III: Fixed-Size Combinations

Combination Sum III adds an additional constraint: we must use exactly k numbers from the range 1-9, and each can be used at most once.

Problem Statement:

Find all valid combinations of k numbers that sum up to n such that:

Only numbers 1 through 9 are used
Each number is used at most once

Example:

Input: k=3, n=7
Output: [[1,2,4]]
Explanation: 1+2+4=7, using exactly 3 numbers

Additional Constraint Handling:

This variant requires tracking two constraints simultaneously:

The running sum must not exceed target
The combination length must not exceed k

We can use both constraints for pruning, making the search more efficient.

combination_sum_3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def combinationSum3(k: int, n: int) -> list[list[int]]:
    """
    Find k numbers from 1-9 (each used once) that sum to n.
    
    Time Complexity: O(C(9,k) * k) ≈ O(9! / (k! * (9-k)!))
    Space Complexity: O(k) for recursion depth
    """
    result = []
    
    def backtrack(start: int, remaining: int, path: list[int]) -> None:
        # Base case: found a valid combination
        if len(path) == k:
            if remaining == 0:
                result.append(path[:])
            return  # Don't continue—we have exactly k elements
        
        # Pruning: if we've exceeded the sum or can't pick enough numbers
        if remaining <= 0:
            return
        
        # Additional pruning: not enough numbers left to fill k slots
        if 9 - start + 1 < k - len(path):
            return
        
        for num in range(start, 10):  # 1 to 9
            # Optimization: if num > remaining, no point continuing
            if num > remaining:
                break
            
            # CHOOSE
            path.append(num)
            
            # EXPLORE (num+1 because each number used at most once)
            backtrack(num + 1, remaining - num, path)
            
            # UNCHOOSE
            path.pop()
    
    backtrack(1, n, [])  # Start from 1
    return result
 
 
# Examples
print(combinationSum3(3, 7))   # [[1, 2, 4]]
print(combinationSum3(3, 9))   # [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
print(combinationSum3(2, 18))  # []  (max is 9+8=17)

Multi-Constraint Pruning

Complexity Analysis Across Variants

Understanding the complexity of Combination Sum variants helps you predict performance and choose appropriate optimizations.

Combination Sum I Complexity:

Time: O(N^(T/M)) where N = |candidates|, T = target, M = min(candidates)
Space: O(T/M) for recursion depth

Combination Sum II Complexity:

Each element used at most once means maximum recursion depth is N (pick all elements).

Time: O(2^N) — each element is either included or excluded
Space: O(N) for recursion depth and path

Combination Sum III Complexity:

We're choosing k elements from 9, with various pruning.

Time: O(C(9,k) × k) = O(9! / (k! × (9-k)!) × k)
Space: O(k) for recursion depth

For k=4 (the maximum useful value since 1+2+...+9=45), this is at most C(9,4)×4 = 126×4 = 504 operations.

Time Complexity Comparison
Variant	Time Complexity	Practical Bound	Notes
Combination Sum I	O(N^(T/M))	Can be large for small M	Sorting + pruning crucial
Combination Sum II	O(2^N)	Manageable for N ≤ 30	Duplicate skipping essential
Combination Sum III	O(C(9,k) × k)	At most ~500 ops	Fixed input range limits search

Why These Problems Are Solvable

Common Pitfalls and Edge Cases

The Combination Sum problems have several subtle gotchas that catch even experienced programmers. Let's catalog them.

Pitfall 1: Forgetting to Copy the Path

# WRONG
result.append(path)  # Appends a reference!

# All entries in result point to the same list
# which gets modified as backtracking continues

# CORRECT
result.append(path[:])  # or list(path) or path.copy()

The path list is reused across recursive calls. Appending the reference means all results share the same list, which ends up empty after all backtracking completes.

Pitfall 2: Off-by-One in Duplicate Skipping

# WRONG
if candidates[i] == candidates[i-1]:  # Missing i > start check!
    continue

# This skips ALL duplicates, even valid ones at different levels

# CORRECT
if i > start and candidates[i] == candidates[i-1]:
    continue

Pitfall 3: Using i+1 vs i for Recursion

Combination Sum I (unlimited reuse): pass i to allow reusing same element
Combination Sum II (single use): pass i+1 to move past used element

Mixing these up gives incorrect results silently—tests might pass for some cases.

Common Mistakes

•Appending path reference instead of copy
•Forgetting to sort before duplicate skipping
•Wrong recursion index (i vs i+1)
•Missing i > start condition
•Not handling empty input or zero target

Edge Cases to Test

•Target equals a single candidate
•Target is 0 (empty combination valid?)
•All candidates larger than target
•Single candidate that divides target
•All identical candidates (e.g., [1,1,1,1])

The Zero Target Trap

Summary: Mastering Combination Sum

The Combination Sum family represents a fundamental backtracking pattern that appears throughout algorithmic problem-solving. Let's consolidate our learning:

Key Takeaways

•The start parameter prevents duplicate combinations — By always choosing from index ≥ start, we ensure each combination is generated exactly once in a canonical order.
•Reuse control: i vs i+1 — Pass 'i' to allow unlimited reuse, pass 'i+1' to enforce single use. This one-character difference changes the entire problem semantics.
•Duplicate handling requires sorting + the i > start check — Sort to group duplicates, then skip when we've already explored a duplicate at the current recursion level.
•Sorting enables early termination — Once candidate > remaining, all subsequent candidates are larger and can be skipped.
•Always copy the path when recording results — The path list is reused; appending a reference causes all results to share the same (eventually empty) list.
•Multi-constraint problems apply all constraints for pruning — Combination Sum III uses both sum and count constraints to dramatically reduce search space.

What's next:

Page Complete

2 / 4