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.
1#
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.