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 all possible combinations of k numbers chosen from the range 1..n. Each combination must contain unique numbers and order does not matter.
Approach 1: Backtracking (Time: O(C(n,k) * k), Space: O(k))
This problem maps directly to backtracking. Build combinations incrementally using a recursive function. Start with an empty path, iterate from the current number to n, add the number to the path, recurse with the next start index, and remove the number after returning. The recursion stops once the path size reaches k, at which point the combination is recorded. The key insight is pruning the search space by always moving forward in the range, preventing duplicates and ensuring combinations remain sorted. The algorithm generates exactly C(n,k) combinations and each takes O(k) time to copy into the result.
This approach relies on recursion and a temporary list that represents the current combination. The maximum recursion depth is k, which keeps the auxiliary space small. Interviewers usually expect this solution because it demonstrates control over recursive state and search-tree exploration.
Approach 2: Iterative Using Bit Masking (Time: O(2^n * n), Space: O(k))
A more mechanical approach is to treat each subset of numbers 1..n as a bitmask. Each integer from 0 to (1 << n) - 1 represents a subset where the i-th bit indicates whether number i+1 is included. Iterate through all masks, count the number of set bits, and collect elements only when the count equals k. This method relies on bit manipulation to represent subsets compactly.
While simple to implement iteratively, this approach scans the entire power set of size 2^n, which becomes expensive as n grows. It is usually less efficient than backtracking because most subsets do not have exactly k elements.
Recommended for interviews: Backtracking is the expected solution. It directly constructs valid combinations instead of enumerating all subsets, resulting in O(C(n,k)) generation. The bitmask approach shows understanding of subset enumeration but is typically considered less optimal for this problem.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(C(n,k) * k) | O(k) | Preferred interview solution when generating combinations directly |
| Iterative Bit Masking | O(2^n * n) | O(k) | Useful for understanding subset enumeration or when iterating all subsets |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,116 views views
Watch 9 more video solutions →Practice Combinations with our built-in code editor and test cases.
Practice on FleetCode