Watch 10 video solutions for Combinations, a medium level problem involving Backtracking. This walkthrough by Ashish Pratap Singh has 1,002,116 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 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.
| 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 |