Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
1 through 9 are used.Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.
Example 2:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.
Example 3:
Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
Constraints:
2 <= k <= 91 <= n <= 60Problem Overview: You need to generate all unique combinations of k numbers from the range 1–9 such that their sum equals n. Each number can be used at most once, and combinations must contain exactly k numbers.
Approach 1: Backtracking (Time: O(C(9,k)), Space: O(k))
This problem naturally fits backtracking. You build combinations incrementally while exploring numbers from 1 to 9. At each step, append the current number to a temporary list, update the remaining sum, and recursively explore the next numbers. Pruning makes this efficient: stop exploring when the remaining sum becomes negative or the combination length exceeds k. Once the combination length reaches k and the remaining sum is 0, record the result. Since the search space only contains numbers 1..9, the recursion tree is small and predictable. This approach works well for problems involving constrained subsets of an array-like sequence where combinations must satisfy a condition.
The key insight is enforcing increasing order during recursion. When you choose a number i, the next recursive call only considers numbers i+1 through 9. This guarantees uniqueness without additional data structures. The recursion depth never exceeds k, so auxiliary space stays small.
Approach 2: Iterative with Bitmasking (Time: O(2^9 * 9), Space: O(1) extra)
Another way is to enumerate every subset of numbers 1..9 using 9-bit masks. Each mask represents whether a number is included. Iterate from 0 to (1 << 9) - 1, count the number of set bits, and compute the subset sum. If the mask contains exactly k numbers and the sum equals n, convert the mask into the corresponding combination. This method avoids recursion entirely and relies on simple bit operations and iteration.
Bitmasking treats the candidate numbers as a fixed-size set. For each mask, check bits using bitwise operations and build the combination. Since the total number of subsets is only 512, the algorithm runs quickly even with repeated checks. It’s a clean iterative alternative when you want deterministic enumeration instead of recursive exploration.
Recommended for interviews: The backtracking approach is what most interviewers expect. It demonstrates control over recursion, pruning, and combination generation—core skills in backtracking and recursion problems. Bitmasking works because the domain is small, but it doesn’t scale as well conceptually. Showing both approaches signals strong understanding of search-space enumeration.
This approach uses backtracking to explore all possible combinations. Start with an empty combination, then add numbers incrementally and explore subsequent possibilities. If the sum of combination exceeds n or if it reaches the required length k, backtracking occurs to explore other potential combinations.
This C code leverages recursion to implement a backtracking solution. It uses the backtrack function recursively to explore combinations of numbers from 1 to 9, which decreases the target sum and the number of numbers to pick. When a valid combination is found (sum equals n and length k), it adds it to the results. Memory management is handled carefully for arrays.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n) because each number has a choice of being included or not.
Space Complexity: O(k) for the recursion stack.
This approach leverages bitmasking to generate all subsets of numbers {1,2,...,9} and filters conceivable combinations by size and sum criteria. It's potentially less intuitive, yet eliminates recursion.
Utilizing bitmasking in C via manual iteration replacement, the core function combine employs increment logic to attempt each mask permutation across numbers [1,2,…,9]. Valid combinations are printed, as demonstrated. Particular attention is paid to inclusive continuity of sequence generation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.
Space Complexity: O(k) due to maintained size of data array.
| Approach | Complexity |
|---|---|
| Backtracking approach | Time Complexity: Space Complexity: |
| Iterative with bitmasking | Time Complexity: Space Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(C(9,k)) | O(k) | Best general solution for generating combinations with constraints |
| Iterative Bitmasking | O(2^9 * 9) | O(1) | Useful when the candidate set is small and fixed |
Combination Sum - Backtracking - Leetcode 39 - Python • NeetCode • 372,069 views views
Watch 9 more video solutions →Practice Combination Sum III with our built-in code editor and test cases.
Practice on FleetCode