Sponsored
Sponsored
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.
1import
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.