Combination Sum III (K Numbers to N)

▶

Steps

setup

Start Backtracking from 1 with empty combination

The algorithm begins by calling backtrack with start=1, an empty combination, and total sum 0. It prepares to explore numbers from 1 to 9.

💡 This initialization sets the stage for exploring all combinations starting from the smallest number.

Line:

backtrack(1, [], 0)

💡 The recursion tree root represents the initial empty state before any numbers are chosen.

traverse

Choose 1 as first number and recurse

The algorithm chooses number 1, adds it to the combination, and calls backtrack with start=2, combination [1], and total=1.

💡 Choosing the smallest number first explores the lowest possible sums early, which helps pruning later.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Adding 1 moves the search forward with a partial combination and updated sum.

traverse

Choose 2 as second number and recurse

Number 2 is chosen next, added to combination [1], making it [1,2], and backtrack is called with start=3 and total=3.

💡 Incrementing start ensures numbers are unique and increasing, avoiding duplicates.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 The combination grows and the sum updates, moving closer to the target.

compare

Choose 3 as third number and check sum bounds

Number 3 is chosen, combination becomes [1,2,3], total sum 6. The algorithm calculates min_sum and max_sum for remaining numbers (0 remaining), then checks if total matches target.

💡 Sum bounds help decide if continuing is worthwhile or if pruning is needed.

Line:

min_sum = (2 * start + remaining - 1) * remaining // 2
max_sum = (2 * 9 - remaining + 1) * remaining // 2
if total + min_sum > n or total + max_sum < n:
    return

💡 With no numbers left to add, total must equal target to be valid.

prune

Reject combination [1,2,3] because sum 6 != 7

Since the combination length equals k but total sum 6 is less than target 7, this path is pruned and backtracking occurs.

💡 Pruning invalid complete combinations avoids unnecessary work.

Line:

if len(comb) == k and total == n:
    res.append(comb[:])
    return

💡 Only combinations with exact sum and length are accepted.

traverse

Try next number 4 at third position

Backtracking to previous call, the algorithm tries number 4 next, making combination [1,2,4] with total 7.

💡 Trying next candidates explores all possible combinations systematically.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Incrementing the last number explores new sums.

insert

Accept combination [1,2,4] because sum 7 == target

Combination length is k=3 and total sum equals target n=7, so [1,2,4] is added to results.

💡 Finding a valid combination is the goal of the algorithm.

Line:

if len(comb) == k and total == n:
    res.append(comb[:])
    return

💡 The algorithm correctly identifies valid solutions.

traverse

Backtrack and try 5 at third position

After accepting [1,2,4], the algorithm backtracks and tries number 5 next, making combination [1,2,5] with total 8.

💡 Backtracking explores all possibilities even after finding valid answers.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Exploring larger sums to check for other valid combinations.

prune

Prune combination [1,2,5] because sum 8 > target 7

Combination length is k=3 but total sum 8 exceeds target 7, so this path is pruned immediately.

💡 Early pruning saves time by stopping exploration of impossible sums.

Line:

if len(comb) > k or total > n:
    return

💡 Sum constraints effectively cut off invalid paths early.

traverse

Backtrack to second number and try 3

Backtracking to second level, the algorithm removes 2 and tries 3 as the second number, combination becomes [1,3], total 4.

💡 Backtracking removes last choice and tries next candidates to explore all combinations.

Line:

comb.pop()
comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Backtracking systematically explores all candidate numbers at each position.

traverse

Try 4 as third number with combination [1,3,4]

Number 4 is chosen as third number, combination is [1,3,4], total sum 8, which exceeds target.

💡 Checking sums after adding each number helps prune early.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Sum exceeds target, so pruning will occur.

prune

Prune combination [1,3,4] because sum 8 > target 7

Combination length is k=3 but total sum 8 exceeds target 7, so this path is pruned.

💡 Pruning invalid sums avoids unnecessary deeper recursion.

Line:

if len(comb) > k or total > n:
    return

💡 Sum constraints effectively prune invalid paths.

traverse

Backtrack to first number and try 2

Backtracking to first level, the algorithm removes 1 and tries 2 as first number, combination [2], total 2.

💡 Backtracking explores all first-level candidates to find all valid combinations.

Line:

comb.pop()
comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Systematic exploration of all starting points.

traverse

Try 3 as second number with combination [2,3]

Number 3 is chosen as second number, combination is [2,3], total sum 5.

💡 Building combinations incrementally to reach target sum.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Partial sums guide the search towards the target.

traverse

Try 4 as third number with combination [2,3,4]

Number 4 is chosen as third number, combination is [2,3,4], total sum 9.

💡 Checking if this combination meets the target sum.

Line:

comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Sum exceeds target, so pruning will occur.

prune

Prune combination [2,3,4] because sum 9 > target 7

Combination length is k=3 but total sum 9 exceeds target 7, so this path is pruned.

💡 Pruning invalid sums avoids unnecessary deeper recursion.

Line:

if len(comb) > k or total > n:
    return

💡 Sum constraints effectively prune invalid paths.

traverse

Backtrack to root and try 3 as first number

Backtracking to root, the algorithm removes 2 and tries 3 as first number, combination [3], total 3.

💡 Backtracking explores all first-level candidates to find all valid combinations.

Line:

comb.pop()
comb.append(i)
backtrack(i + 1, comb, total + i)

💡 Systematic exploration of all starting points.

backtracking

No valid combinations found beyond this point, backtrack to root

The algorithm tries further numbers but pruning and sum checks prevent any new valid combinations. It backtracks fully to root.

💡 Backtracking completes after exploring all candidates.

Line:

backtrack(1, [], 0)
return res

💡 All valid combinations have been found and collected.

reconstruct

Return final result with all valid combinations

The algorithm returns the collected results [[1,2,4]] as the final answer.

💡 Returning the collected answers completes the algorithm.

Line:

return res

💡 The final output contains all valid combinations found.

from typing import List

def combinationSum3(k: int, n: int) -> List[List[int]]:
    res = []
    def backtrack(start: int, comb: List[int], total: int):
        # STEP 9: Prune if combination too long or sum too big
        if len(comb) > k or total > n:
            return
        remaining = k - len(comb)
        # STEP 4: Calculate min sum of next 'remaining' numbers
        min_sum = (2 * start + remaining - 1) * remaining // 2
        # STEP 4: Calculate max sum of next 'remaining' numbers
        max_sum = (2 * 9 - remaining + 1) * remaining // 2
        # STEP 4: Prune if sum bounds exclude target
        if total + min_sum > n or total + max_sum < n:
            return
        # STEP 7: If combination complete and sum matches, add to results
        if len(comb) == k and total == n:
            res.append(comb[:])
            return
        # STEP 2: Try numbers from start to 9
        for i in range(start, 10):
            comb.append(i)  # STEP 3: Choose number i
            backtrack(i + 1, comb, total + i)  # STEP 3: Recurse
            comb.pop()  # STEP 3: Backtrack
    backtrack(1, [], 0)  # STEP 1: Initial call
    return res

📊

Combination Sum III (K Numbers to N) - Watch the Algorithm Execute, Step by Step

Watching the recursion tree unfold with pruning reveals how the algorithm efficiently narrows down the search space, making it easier to understand backtracking with constraints.

enteringstart=1comb=[]total=0

Call Path (current → root)

backtrack(1, [], 0)

Remaining

123456789

enteringstart=2comb=[1]total=1

Call Path (current → root)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Remaining

23456789

Partial: [1]

enteringstart=3comb=[1,2]total=3

Call Path (current → root)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Remaining

3456789

Partial: [1, 2]

choosingstart=4comb=[1,2,3]total=6

Call Path (current → root)

backtrack(4, [1, 2, 3], 6)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Partial: [1, 2, 3]

backtrackingstart=4comb=[1,2,3]total=6

Call Path (current → root)

backtrack(4, [1, 2, 3], 6)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Tried

3

Partial: [1, 2, 3]

✂ Combination length reached but sum 6 != 7

enteringstart=4comb=[1,2,4]total=7

Call Path (current → root)

backtrack(4, [1, 2, 4], 7)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Partial: [1, 2, 4]

backtrackingstart=4comb=[1,2,4]total=7

Call Path (current → root)

backtrack(4, [1, 2, 4], 7)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Tried

4

Partial: [1, 2, 4]

Found 1: [1,2,4]

enteringstart=5comb=[1,2,5]total=8

Call Path (current → root)

backtrack(5, [1, 2, 5], 8)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Partial: [1, 2, 5]

Found 1: [1,2,4]

backtrackingstart=5comb=[1,2,5]total=8

Call Path (current → root)

backtrack(5, [1, 2, 5], 8)

backtrack(3, [1, 2], 3)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Tried

5

Partial: [1, 2, 5]

✂ Sum 8 exceeds target 7

Found 1: [1,2,4]

enteringstart=3comb=[1,3]total=4

Call Path (current → root)

backtrack(3, [1, 3], 4)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Tried

2

Remaining

3456789

Partial: [1, 3]

Found 1: [1,2,4]

choosingstart=5comb=[1,3,4]total=8

Call Path (current → root)

backtrack(5, [1, 3, 4], 8)

backtrack(3, [1, 3], 4)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Partial: [1, 3, 4]

Found 1: [1,2,4]

backtrackingstart=5comb=[1,3,4]total=8

Call Path (current → root)

backtrack(5, [1, 3, 4], 8)

backtrack(3, [1, 3], 4)

backtrack(2, [1], 1)

backtrack(1, [], 0)

Tried

4

Partial: [1, 3, 4]

✂ Sum 8 exceeds target 7

Found 1: [1,2,4]

enteringstart=2comb=[2]total=2

Call Path (current → root)

backtrack(2, [2], 2)

backtrack(1, [], 0)

Tried

1

Remaining

3456789

Partial: [2]

Found 1: [1,2,4]

enteringstart=4comb=[2,3]total=5

Call Path (current → root)

backtrack(4, [2, 3], 5)

backtrack(2, [2], 2)

backtrack(1, [], 0)

Remaining

456789

Partial: [2, 3]

Found 1: [1,2,4]

choosingstart=5comb=[2,3,4]total=9

Call Path (current → root)

backtrack(5, [2, 3, 4], 9)

backtrack(4, [2, 3], 5)

backtrack(2, [2], 2)

backtrack(1, [], 0)

Partial: [2, 3, 4]

Found 1: [1,2,4]

backtrackingstart=5comb=[2,3,4]total=9

Call Path (current → root)

backtrack(5, [2, 3, 4], 9)

backtrack(4, [2, 3], 5)

backtrack(2, [2], 2)

backtrack(1, [], 0)

Tried

4

Partial: [2, 3, 4]

✂ Sum 9 exceeds target 7

Found 1: [1,2,4]

enteringstart=3comb=[3]total=3

Call Path (current → root)

backtrack(3, [3], 3)

backtrack(1, [], 0)

Tried

12

Remaining

456789

Partial: [3]

Found 1: [1,2,4]

backtrackingstart=10comb=[]total=0

Call Path (current → root)

backtrack(1, [], 0)

Tried

123456789

Found 1: [1,2,4]

Answer: [[1,2,4]]

Total calls: 19 · Pruned: 6

Key Takeaways

✓ Pruning with sum bounds drastically reduces the search space.

Without pruning, the algorithm would explore many impossible combinations, making it inefficient.

✓ Backtracking systematically explores all combinations by incrementally building and undoing choices.

Seeing the recursion tree helps understand how the algorithm tries all possibilities without repetition.

✓ Valid combinations are only accepted when both length and sum constraints are exactly met.

This strict acceptance criteria ensures correctness and is easier to grasp visually than from code alone.

Practice

1. Consider the following Python code implementing letter case permutation using backtracking with in-place modification. What is the final output when the input string is "a1b"?

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]  # revert to original
    backtrack(0)
    return res

print(letterCasePermutation("a1b"))

easy

A. ['a1b', 'a1B', 'A1B', 'A1b']

B. ['a1b', 'A1b', 'a1B', 'A1B']

C. ['a1b', 'a1B', 'A1b', 'A1B']

D. ['A1b', 'a1b', 'A1B', 'a1B']

Solution

1. Step 1: Trace backtrack calls for input "a1b"

   Index 0 is 'a' (letter), toggled to 'a' then 'A'. Index 1 is '1' (digit), skipped. Index 2 is 'b' (letter), toggled to 'b' then 'B'.

2. Step 2: Collect permutations in order

   Order of appending: 'a1b', 'a1B', 'A1b', 'A1B'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected toggling order [OK]

Hint: Digits skip toggling; letters toggle lower then upper [OK]

Common Mistakes:

• Swapping order of uppercase/lowercase calls
• Misplacing digit handling

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

4. Examine the following buggy code snippet for letter case permutation. Which line contains the subtle bug that causes incorrect results on inputs with digits?

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            arr[i] = arr[i].upper()  # BUG: digits have no case
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]
    backtrack(0)
    return res

medium

A. Line with 'if i == len(arr):'

B. Line with 'arr[i] = arr[i].upper() # BUG: digits have no case'

C. Line with 'if arr[i].isdigit():'

D. Line with 'arr[i] = s[i]' to revert changes

Solution

1. Step 1: Analyze digit handling

   Digits have no uppercase or lowercase forms, so calling upper() on a digit is unnecessary and incorrect.

2. Step 2: Identify bug impact

   Modifying digits causes incorrect permutations or corrupted results; digits should be left unchanged and recursion called directly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Digits must be skipped, not toggled [OK]

Hint: Digits must not be modified or toggled [OK]

Common Mistakes:

• Forgetting to revert changes
• Modifying digits as letters

5. Suppose the problem is modified so that puzzles can have repeated letters and words can be counted multiple times if they match multiple subsets of the puzzle letters. Which modification to the optimal bitmask + trie approach correctly handles this variant?

hard

A. Preprocess puzzles to remove duplicates and apply the original algorithm unchanged.

B. Modify dfs to not require the puzzle's first letter to be present in the word and allow counting multiple matches per word.

C. Enumerate all subsets of puzzle letters including duplicates and sum counts from trie traversal without filtering first letter.

D. Use a multiset trie that stores counts for repeated letters and traverse all subsets including duplicates.

Solution

1. Step 1: Understand variant requirements

   Repeated letters in puzzles and multiple counting per word require handling multisets, not just sets.

2. Step 2: Modify data structure and traversal

   A multiset trie that stores counts for repeated letters and traverses all subsets including duplicates correctly counts all matches.

3. Step 3: Why other options fail

   Ignoring first letter breaks mandatory condition; removing duplicates loses information; naive enumeration is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Multiset trie handles repeated letters and multiple counts correctly [OK]

Hint: Multiset trie needed for repeated letters and multiple counts [OK]

Common Mistakes:

• Ignoring repeated letters
• Removing duplicates incorrectly
• Dropping first letter condition