Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= nProblem Overview: Given two integers n and k, generate every possible combination of k numbers chosen from the range 1..n. Order inside a combination does not matter, so [1,2] and [2,1] represent the same result and only one should appear.
Approach 1: Backtracking (Time: O(C(n,k) * k), Space: O(k))
This is the standard solution and the one most interviewers expect. Use backtracking to build combinations incrementally. Start from a number, add it to a temporary list, and recursively choose the next numbers from the remaining range. When the current list size reaches k, record the combination. The key insight is that each recursive call restricts the next candidate range, preventing duplicates and preserving ascending order. The recursion depth never exceeds k, and the algorithm generates exactly C(n,k) valid combinations.
Pruning improves efficiency: if you already selected m numbers and there are fewer than k - m numbers left, you can stop exploring that branch. This avoids unnecessary recursive calls when the remaining elements cannot complete a valid combination.
Approach 2: Iterative Approach Using Bit Masking (Time: O(2^n * n), Space: O(k))
This method treats each subset of numbers as a binary mask. For every integer from 0 to (1 << n) - 1, the binary representation indicates which numbers are included. Count the set bits in the mask; if exactly k bits are set, build the corresponding combination by checking each bit position. This relies on bit manipulation and is conceptually simple because it enumerates all subsets.
The downside is that it explores the full subset space of size 2^n, even though only C(n,k) results are needed. For large n, this becomes inefficient compared to targeted generation. Still, it is useful when practicing subset enumeration or when bit operations simplify implementation.
Recommended for interviews: The backtracking approach is the expected solution. It directly models the combinatorial search and generates only valid results, giving optimal output-sensitive complexity of O(C(n,k) * k). Bit masking demonstrates knowledge of recursion alternatives and subset enumeration, but it is rarely the preferred production or interview solution.
This method uses a backtracking technique, where we recursively build each combination by adding numbers incrementally and backtrack whenever we've constructed combinations of size k or cannot extend further.
This solution involves a recursive function backtrack that constructs combinations by adding candidates one by one and proceeds only if the current set can lead to a combination, which ensures our search tree doesn't explore invalid paths. Once a combination of size k is completed, it's stored in the result set.
Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.
Bit masking provides a novel way to generate combinations by representing choice decisions (e.g., pick or skip) in binary. A bit mask is applied to the set of numbers [1...n], and for each bit position, if the bit is set, that number is included in the combination.
This code generates all possible bit masks for integers from 0 to 2n-1, checking for those that have exactly k bits set. The function __builtin_popcount is used to count the number of set bits in the mask, indicating how many items in the set are chosen for a combination.
Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.
We design a function dfs(i), which represents starting the search from number i, with the current search path as t, and the answer as ans.
The execution logic of the function dfs(i) is as follows:
t equals k, then add the current search path to the answer and return.i \gt n, it means the search has ended, return.i to the search path t, and then continue the search, i.e., execute dfs(i + 1), and then remove the number i from the search path t; or we do not add the number i to the search path t, and directly execute dfs(i + 1).The above method is actually enumerating whether to select the current number or not, and then recursively searching the next number. We can also enumerate the next number j to be selected, where i leq j leq n. If the next number to be selected is j, then we add the number j to the search path t, and then continue the search, i.e., execute dfs(j + 1), and then remove the number j from the search path t.
In the main function, we start the search from number 1, i.e., execute dfs(1).
The time complexity is (C_n^k times k), and the space complexity is O(k). Here, C_n^k represents the combination number.
Similar problems:
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time. |
| Iterative Approach Using Bit Masking | Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count. |
| Backtracking (Two Ways) | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(C(n,k) * k) | O(k) | Best general solution. Generates only valid combinations and scales well for typical constraints. |
| Iterative Bit Masking | O(2^n * n) | O(k) | Useful when practicing subset enumeration or when n is small. |
Combinations - Leetcode 77 - Python • NeetCode • 92,125 views views
Watch 9 more video solutions →Practice Combinations with our built-in code editor and test cases.
Practice on FleetCode