Sponsored
Sponsored
This approach uses backtracking to explore all possible combinations. Start with an empty combination, then add numbers incrementally and explore subsequent possibilities. If the sum of combination exceeds n or if it reaches the required length k, backtracking occurs to explore other potential combinations.
Time Complexity: O(2^n) because each number has a choice of being included or not.
Space Complexity: O(k) for the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4void backtrack(int k, int n, int start, int* path, int pathSize, int** results, int* returnSize) {
5 if (k == 0 && n == 0) {
6 results[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
7 for(int i = 0; i < pathSize; i++) {
8 results[*returnSize][i] = path[i];
9 }
10 (*returnSize)++;
11 return;
12 }
13 for (int i = start; i <= 9; i++) {
14 if (i > n) break;
15 path[pathSize] = i;
16 backtrack(k - 1, n - i, i + 1, path, pathSize + 1, results, returnSize);
17 }
18}
19
20int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
21 int path[9];
22 int** results = malloc(100 * sizeof(int*));
23 *returnSize = 0;
24 backtrack(k, n, 1, path, 0, results, returnSize);
25 *returnColumnSizes = malloc(sizeof(int) * (*returnSize));
26 for (int i = 0; i < (*returnSize); i++) {
27 (*returnColumnSizes)[i] = k;
28 }
29 return results;
30}
31
32int main() {
33 int size;
34 int* columnSizes;
35 int** results = combinationSum3(3, 7, &size, &columnSizes);
36 for (int i = 0; i < size; i++) {
37 printf("[");
38 for (int j = 0; j < columnSizes[i]; j++) {
39 printf("%d", results[i][j]);
40 if (j < columnSizes[i] - 1) printf(", ");
41 }
42 printf("]\n");
43 free(results[i]);
44 }
45 free(results);
46 free(columnSizes);
47 return 0;
48}This C code leverages recursion to implement a backtracking solution. It uses the backtrack function recursively to explore combinations of numbers from 1 to 9, which decreases the target sum and the number of numbers to pick. When a valid combination is found (sum equals n and length k), it adds it to the results. Memory management is handled carefully for arrays.
This approach leverages bitmasking to generate all subsets of numbers {1,2,...,9} and filters conceivable combinations by size and sum criteria. It's potentially less intuitive, yet eliminates recursion.
Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.
Space Complexity: O(k) due to maintained size of data array.
1#
Utilizing bitmasking in C via manual iteration replacement, the core function combine employs increment logic to attempt each mask permutation across numbers [1,2,…,9]. Valid combinations are printed, as demonstrated. Particular attention is paid to inclusive continuity of sequence generation.