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 <= nThe #77 Combinations problem asks you to generate all possible combinations of k numbers chosen from the range 1..n. The most effective strategy is backtracking, a technique that incrementally builds candidates and explores all valid possibilities.
Start with an empty path and recursively add the next possible number. At each step, choose a number, append it to the current combination, and continue exploring until the combination size reaches k. Once it does, record the combination and backtrack by removing the last element to explore other choices.
An important optimization is pruning the recursion when there are not enough remaining numbers left to reach size k. This avoids unnecessary exploration and improves performance.
The backtracking tree explores all valid selections of k elements from n, resulting in roughly C(n, k) combinations. The approach is efficient for generating combinations while maintaining manageable recursion depth.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking | O(C(n, k) * k) | O(k) recursion depth (excluding output) |
Ashish Pratap Singh
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.
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.
1#include <iostream>
2#include <vector>
3
4void backtrack(int n, int k, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
5 if (current.size() == k) {
6 result.push_back(current);
7 return;
8 }
9 for (int i = start; i <= n; ++i) {
10 current.push_back(i);
11 backtrack(n, k, i + 1, current, result);
12 current.pop_back();
13 }
14}
15
16std::vector<std::vector<int>> combine(int n, int k) {
17 std::vector<std::vector<int>> result;
18 std::vector<int> current;
19 backtrack(n, k, 1, current, result);
20 return result;
21}
22
23int main() {
24 int n = 4, k = 2;
25 std::vector<std::vector<int>> combinations = combine(n, k);
26 for (const auto& combo : combinations) {
27 std::cout << "[";
28 for (size_t i = 0; i < combo.size(); ++i) {
29 std::cout << combo[i];
30 if (i < combo.size() - 1) std::cout << ", ";
31 }
32 std::cout << "]\n";
33 }
34 return 0;
35}This solution uses C++'s vector class efficiently to manage list operations, performing the recursion similar to the C solution. The backtrack function keeps expanding the current vector until a combination of size k is constructed, then it's added to the results.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach for the Combinations problem is backtracking. It builds combinations step by step and explores all valid selections while pruning branches that cannot reach size k. This ensures we only generate valid combinations without unnecessary computation.
A dynamic list or array is typically used to maintain the current combination while exploring recursion. The final results are stored in a list of lists. Recursion and backtracking manage the exploration of possibilities efficiently.
Yes, combination generation problems frequently appear in technical interviews, including FAANG-style interviews. They test understanding of recursion, backtracking, pruning, and combinatorial thinking.
Yes, combinations can also be generated using iterative techniques or bitmasking. However, backtracking is the most intuitive and commonly used approach because it naturally models the decision tree of choosing elements.
In Java, we use integer masks with bit operations to select combinations. This lets us represent which elements are picked using bit positions, and only add groups of elements with k set bits.