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 <stdio.h>
2#include <stdlib.h>
3
4void backtrack(int n, int k, int start, int* current, int curr_size, int** result, int* returnSize, int* returnColumnSizes) {
5 if (curr_size == k) {
6 result[*returnSize] = (int*) malloc(k * sizeof(int));
7 for (int i = 0; i < k; ++i) {
8 result[*returnSize][i] = current[i];
9 }
10 returnColumnSizes[*returnSize] = k;
11 (*returnSize)++;
12 return;
13 }
14 for (int i = start; i <= n; ++i) {
15 current[curr_size] = i;
16 backtrack(n, k, i + 1, current, curr_size + 1, result, returnSize, returnColumnSizes);
17 }
18}
19
20int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
21 int max_combinations = 1;
22 for (int i = 0; i < k; i++) {
23 max_combinations *= (n - i) / (i + 1);
24 }
25 int** result = (int**) malloc(max_combinations * sizeof(int*));
26 int* current = (int*) malloc(k * sizeof(int));
27 *returnSize = 0;
28 *returnColumnSizes = (int*) malloc(max_combinations * sizeof(int));
29 backtrack(n, k, 1, current, 0, result, returnSize, *returnColumnSizes);
30 free(current);
31 return result;
32}
33
34int main() {
35 int returnSize;
36 int* returnColumnSizes;
37 int n = 4, k = 2;
38 int** combinations = combine(n, k, &returnSize, &returnColumnSizes);
39 for (int i = 0; i < returnSize; i++) {
40 printf("[");
41 for (int j = 0; j < returnColumnSizes[i]; j++) {
42 printf("%d", combinations[i][j]);
43 if (j < returnColumnSizes[i] - 1) printf(", ");
44 }
45 printf("]\n");
46 free(combinations[i]);
47 }
48 free(combinations);
49 free(returnColumnSizes);
50 return 0;
51}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.
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.
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.