Combination Sum III
Problem
Given two integers k and n, return all possible combinations of k numbers that add up to n, where only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
- 2 ≤ k ≤ 9
- 1 ≤ n ≤ 60
Example
k = 3, n = 7[[1,2,4]]The brute-force approach would try all combinations of numbers from 1 to 9 of length k and check if their sum equals n, which is inefficient. The backtracking approach incrementally builds combinations, pruning paths early when the sum exceeds n or the combination length reaches k. For example, starting from 1, the algorithm tries adding 2 and 4 to reach the sum 7 with length 3, which is a valid combination and added to the result. It then backtracks to explore other possibilities, but prunes any path where the sum exceeds 7 or the length exceeds 3.
Approach
Straightforward Solution
A brute-force approach would generate all subsets of numbers 1 to 9 and filter those with length k and sum n. This approach is O(2^9) = O(512) in the worst case, which is feasible but inefficient and does not prune early.
Core Observation
The problem requires enumerating all unique combinations of k distinct numbers from 1 to 9 that sum to n. This is a classic combinatorial search problem with constraints on combination length and sum.
Path to Optimal
PreviewThe key insight is to use backtracking to build combinations incrementally, pruning any path where the sum exceeds n or the length exceeds k. By starting from the smallest number and moving upwards, the algorithm avoids duplicates and ensures combinations are unique and sorted…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive backtracking function that tries numbers from the current start to 9, adding each to the current path if it does not exceed the target sum. When the path length reaches k, check if the sum equals n and add a copy of the path to the result if so…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(C(9, k))
The algorithm explores combinations of size k from 9 numbers, which is bounded by the binomial coefficient C(9, k). Early pruning reduces unnecessary exploration, making the practical runtime efficient.
Space
O(k)
The recursion stack and path list grow up to size k, which is the maximum combination length, representing the auxiliary space used during backtracking.
Pattern Spotlight
Backtracking (State Restoration)
For combination problems with constraints, use backtracking with incremental construction and early pruning, always restoring state after exploring each choice to enable exhaustive yet efficient search.
Solution
| 1 | class Solution: |
| 2 | def combinationSum3(self, k: int, n: int) -> List[List[int]]: |
| 3 | result = [] |
| 4 | |
| 5 | def backtrack(start, path, total): |
| 6 | if len(path) == k: |
| 7 | if total == n: |
| 8 | result.append(path.copy()) |
| 9 | return |
| 10 | |
| 11 | for num in range(start, 10): |
| 12 | if total + num > n: |
| 13 | break |
| 14 | |
| 15 | path.append(num) |
| 16 | backtrack(num + 1, path, total + num) |
| 17 | path.pop() |
| 18 | |
| 19 | backtrack(1, [], 0) |
| 20 | return result |
Step-by-Step Solution
Initialize Result Container to Collect Valid Combinations
| 3 | result = [] |
Objective
To prepare a list that will store all valid combinations found during the backtracking process.
Key Insight
Having a dedicated result list allows the algorithm to accumulate valid solutions incrementally. This separation of concerns keeps the recursive function focused on exploration and validation, while the result list collects final answers.
Interview Quick-Check
Core Logic
The result list stores all valid combinations found by the backtracking function.
State & Boundaries
The result list is initialized once before recursion begins and returned after all exploration completes.
Explore Combinations Recursively with Early Pruning
To recursively build combinations by adding numbers from the current start to 9, pruning paths that exceed the target sum or combination length.
Initiate Backtracking and Return All Valid Combinations
To start the recursive exploration from number 1 with an empty path and zero sum, and return the collected results after completion.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
path.pop()Remove the last number from the path to backtrack.
This 'un-choose' step restores the path state, enabling exploration of alternative combinations without interference from previous choices.
result.append(path.copy())Add a copy of the current path to the result list.
Copying the path is essential because the path list is mutable and will be modified during backtracking; storing a copy preserves the valid combination.
backtrack(num + 1, path, total + num)Recursively call backtrack with updated start, path, and sum.
This recursive call explores deeper combinations, advancing the start to avoid duplicates and updating the sum to reflect the new path.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why is it necessary to backtrack (remove the last number) after each recursive call in this algorithm?
See the answer with Pro.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Combination Sum III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Combination Sum III drill