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:
- The subset size (count) is exactly
k. - 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 ( 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
-
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.
-
Base Cases:
- If
len(current_combination) == kandcurrent_sum == n, we found a valid solution; add to results. - If
len(current_combination) >= korcurrent_sum > n, stop this branch (prune).
- If
-
Recursive Step: Iterate through numbers from
start_indexup to 9. For each number:- Add it to the combination and update sum.
- Recurse with
i + 1as the new start index. - Backtrack (remove last element) before trying the next loop iteration.
-
Optimization: While not strictly necessary given , I will check if remaining numbers are sufficient to reach count
k. Specifically,(9 - i + 1)is the max available items; we need at leastk - len(current_combination). If fewer remain than needed, break loop.
Complexity Analysis
- Time: 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 (), this fits well within time limits for any
n. - Space: 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
nis too small or large for the givenk, the base case condition (sum == n) will never be met at depthk. 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
nis small butkrequires large minimum sum (e.g., min sum for k=3 is ), any input withn < 6will 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.