Domain 2MediumCORE

Combination Sum III

We are looking for all unique subsets of numbers from the range [1, 9] that satisfy two specific constraints: 1. The subset size (count) is exactly k. 2. The sum of elements in the subset equals n.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Backtracking

216. Combination Sum III

Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 60.6%


Problem Breakdown

We are looking for all unique subsets of numbers from the range [1, 9] that satisfy two specific constraints:

  1. The subset size (count) is exactly k.
  2. The sum of elements in the subset equals n.

Key Constraints & Edge Cases:

  • Input Domain: We are restricted to digits 1 through 9 only. No zeros, no negatives, no numbers > 9.
  • Uniqueness: Each number within a combination can be used at most once (e.g., [2, 3] is valid, but [2, 2] is not). The result list must contain unique combinations; we cannot return both [1, 2, 4] and [4, 2, 1].
  • Output Order: Combinations can be returned in any order. However, internally maintaining a sorted order (ascending) within each combination helps prevent duplicates naturally during generation.

Intuition

If I were to approach this naively, I might think of generating all permutations or subsets and filtering them at the end. Since there are only 9 possible numbers (29=5122^9 = 512 total subsets), brute-forcing isn’t strictly impossible in terms of raw operations, but it’s inefficient because we’d be checking invalid branches (wrong sum) before pruning them.

The core insight here is that this is a search problem where the order doesn’t matter for combinations—only membership does. This screams Backtracking. To avoid duplicates like [1, 2] and [2, 1], I must enforce an ordering constraint: once I pick number x, subsequent numbers in my combination must be strictly greater than x. By iterating through candidates starting from the last picked index + 1 (or a fixed start), we ensure every generated list is sorted ascendingly.

I also need to prune branches early. If adding a candidate makes the sum exceed n before reaching depth k, that path is dead and I should stop exploring it immediately. This keeps the recursion tree lean.

Approach

  1. Define State: A recursive function needs three pieces of state:

    • start_index: The smallest number we are allowed to pick next (to ensure uniqueness).
    • current_combination: List tracking numbers picked so far.
    • current_sum: Running total of the combination.
  2. Base Cases:

    • If len(current_combination) == k and current_sum == n, we found a valid solution; add to results.
    • If len(current_combination) >= k or current_sum > n, stop this branch (prune).
  3. Recursive Step: Iterate through numbers from start_index up to 9. For each number:

    • Add it to the combination and update sum.
    • Recurse with i + 1 as the new start index.
    • Backtrack (remove last element) before trying the next loop iteration.
  4. Optimization: While not strictly necessary given N=9N=9, I will check if remaining numbers are sufficient to reach count k. Specifically, (9 - i + 1) is the max available items; we need at least k - len(current_combination). If fewer remain than needed, break loop.

Complexity Analysis

  • Time: O(2N)O(2^N) where N is the range of numbers (fixed at 9). More accurately, it’s proportional to the number of valid nodes in our recursion tree. Since we prune invalid sums and enforce ordering, we visit only relevant subsets. Given constraints (k≤9k \le 9), this fits well within time limits for any n.
  • Space: O(k)O(k) stack space due to recursion depth (max depth is k). We also store the output list which takes proportional space to the number of valid combinations found, but that’s standard return value overhead.

Solution

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []
        
        # Helper function for backtracking
        def backtrack(start_index, current_combination, current_sum):
            # Base case 1: Combination is full size and sum matches target
            if len(current_combination) == k and current_sum == n:
                results.append(list(current_combination))
                return
            
            # Pruning: If we've exceeded the count or sum limit for this branch, stop.
            # Also check remaining available numbers to avoid unnecessary recursion depth
            if len(current_combination) >= k or current_sum > n:
                return

            # Iterate through candidates from start_index up to 9
            for i in range(start_index, 10): 
                # Optimization: If we pick 'i', check if remaining numbers are enough.
                # We need (k - len(current_combination) + 1) more items including this one?
                # Actually simpler prune is just sum logic or count logic inside loop.
                
                current_combination.append(i)
                backtrack(i + 1, current_combination, current_sum + i)
                current_combination.pop()

        backtrack(1, [], 0)
        return results

Edge Cases Handled

  • No Solution: If n is too small or large for the given k, the base case condition (sum == n) will never be met at depth k. The function returns an empty list.
  • Max Range Usage (Example 5): When k=9, n=45, the loop runs until index 10, picking every number exactly once. Logic holds because we increment start_index to prevent reusing numbers in a single combination.
  • Impossible Sum: If n is small but k requires large minimum sum (e.g., min sum for k=3 is 1+2+3=61+2+3=6), any input with n < 6 will result in no matches, handled naturally by the pruning logic (current_sum > n).
  • Duplicate Combinations: By enforcing strictly increasing indices via backtrack(i + 1), we ensure [1, 2] is generated but never [2, 1]. This guarantees unique combinations in the output list.