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 must pick exactly k distinct numbers from 1..9 so their sum equals n. Each number can be used once, and the result should include all valid combinations without duplicates.
Approach 1: Backtracking (O(2^9) time, O(k) space)
This problem naturally fits backtracking. Start from number 1 and recursively build combinations by choosing the next number and reducing the remaining sum. Stop exploring a path when the combination size exceeds k or the sum becomes negative. When the combination length equals k and the remaining sum is 0, record the result. Since the search space only includes numbers 1..9, the recursion tree is small, making the effective time complexity about O(2^9) and space O(k) for the recursion stack and current path.
Approach 2: Iterative with Bitmasking (O(2^9 * 9) time, O(1) space)
You can enumerate every subset of numbers 1..9 using a bitmask from 0 to (1<<9) - 1. Each bit represents whether a number is included in the subset. For each mask, iterate through the bits, count how many numbers are chosen, and compute their sum. If the subset size equals k and the sum equals n, add it to the result. This approach treats the problem like a subset enumeration on an array of numbers and uses a classic bitmasking pattern. Time complexity is O(2^9 * 9) because every mask checks up to nine bits, while space complexity is O(1) excluding the output.
Recommended for interviews: Backtracking is the expected approach. Interviewers want to see how you prune invalid states early (sum exceeded, size exceeded) and generate combinations without duplicates. The bitmasking method demonstrates good understanding of subset enumeration, but backtracking better shows your ability to control the search space and write clean recursive logic.
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.
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.
Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.
Space Complexity: O(k) due to maintained size of data array.
We design a function dfs(i, s), which represents that we are currently enumerating the number i, and there are still numbers with a sum of s to be enumerated. The current search path is t, and the answer is ans.
The execution logic of the function dfs(i, s) is as follows:
Approach One:
s = 0 and the length of the current search path t is k, it means that a group of answers has been found. Add t to ans and then return.i \gt 9 or i \gt s or the length of the current search path t is greater than k, it means that the current search path cannot be the answer, so return directly.i to the search path t, and then continue to search, i.e., execute dfs(i + 1, s - i). After the search is completed, remove i from the search path t; we can also choose not to add the number i to the search path t, and directly execute dfs(i + 1, s).Python
Java
C++
Go
TypeScript
JavaScript
Rust
C#
We can use a binary integer of length 9 to represent the selection of numbers 1 to 9, where the i-th bit of the binary integer represents whether the number i + 1 is selected. If the i-th bit is 1, it means that the number i + 1 is selected, otherwise, it means that the number i + 1 is not selected.
We enumerate binary integers in the range of [0, 2^9). For the currently enumerated binary integer mask, if the number of 1s in the binary representation of mask is k, and the sum of the numbers corresponding to 1 in the binary representation of mask is n, it means that the number selection scheme corresponding to mask is a group of answers. We can add the number selection scheme corresponding to mask to the answer.
The time complexity is O(2^9 times 9), and the space complexity is O(k).
Similar problems:
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Backtracking approach | Time Complexity: Space Complexity: |
| Iterative with bitmasking | Time Complexity: Space Complexity: |
| Pruning + Backtracking (Two Approaches) | — |
| Binary Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^9) | O(k) | Best general solution for generating valid combinations with pruning |
| Iterative Bitmasking | O(2^9 * 9) | O(1) | When enumerating all subsets or demonstrating bitmask subset techniques |
Combination Sum iii | LeetCode 216 | C++, Java, Python • Knowledge Center • 13,429 views views
Watch 9 more video solutions →Practice Combination Sum III with our built-in code editor and test cases.
Practice on FleetCode