Watch 10 video solutions for Combinations, a medium level problem involving Backtracking. This walkthrough by NeetCode has 92,125 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |