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}

1