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 code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]?

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Enumerate all non-empty subsets and their OR

   Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

2. Step 2: Identify max OR and count subsets with that OR

   Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted 5 subsets with max OR 3 -> matches 5 [OK]

Hint: Count subsets with OR equal to max OR -> 5 [OK]

Common Mistakes:

• Counting empty subset as valid
• Miscounting subsets with max OR

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. What is the worst-case time complexity of the optimized dynamic programming solution for the Largest Divisible Subset problem, where n is the number of elements in the input array?

medium

A. O(n^2) due to nested loops checking divisibility pairs

B. O(2^n) because all subsets are considered

C. O(n^3) because of triple nested loops for subset checks

D. O(n log n) due to sorting and linear DP

Solution

1. Step 1: Identify main operations

   Sorting takes O(n log n). The DP uses two nested loops: outer loop over n elements, inner loop up to i elements.

2. Step 2: Analyze nested loops

   Each pair (i,j) is checked once, resulting in O(n^2) divisibility checks. Early break may speed up in practice but worst case remains O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP nested loops dominate complexity [OK]

Hint: DP nested loops -> O(n^2) worst case [OK]

Common Mistakes:

• Confusing sorting time as dominant (O(n log n))
• Assuming triple nested loops due to subset checks
• Thinking brute force complexity applies to DP

4. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n

5. Suppose the problem is changed so that candidates can be reused unlimited times (unlike original no reuse). Which modification to the backtracking algorithm correctly adapts to this change?

hard

A. Change recursive call from backtrack(i + 1, ...) to backtrack(i, ...) to allow reuse of the same candidate

B. Keep backtrack(i + 1, ...) but remove duplicate skipping to allow repeated combinations

C. Add a global visited set to prevent reusing candidates in the same combination

D. Sort candidates and prune only when candidate >= target, but keep recursion unchanged

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same candidate index can be chosen multiple times in the same combination.

2. Step 2: Modify recursion call

   Changing recursive call from backtrack(i + 1, ...) to backtrack(i, ...) allows the same candidate to be reused multiple times.

3. Step 3: Keep duplicate skipping and pruning as before

   Duplicate skipping still applies to avoid repeated combinations, and pruning remains to optimize.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recurse with same index to allow reuse [OK]

Hint: Reuse means recurse with same index, not next index [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Using visited set breaks reuse logic
• Pruning incorrectly changes conditions