Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 216. Combination Sum III

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4537983.html

題目：


解答：

#define MAX_SIZE 1000
 
int dfs(int k, int n, int pos, int *tbuf, int tlen, int **rbuf, int *rlen)
{
    int i = 0;
 
    if (tlen == k) {
        for (i = 0; i < k; i++) {
            n -= tbuf[i];
        }
 
        if (n == 0) {
            memcpy(rbuf[*rlen], tbuf, sizeof(int) * k);
            *rlen += 1;
        }
 
        tlen -= 1;
        return 0;
    }
 
    for (i = pos + 1; i <= 9; i++) {
        tbuf[tlen] = i;
 
        tlen += 1;
        dfs(k, n, i, tbuf, tlen, rbuf, rlen);
        tlen -= 1;
    }
 
    return 0;
}
 
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** combinationSum3(int k, int n, int *returnSize, int **returnColumnSizes)
{
    int i = 0;
    int len = 0;
    int **rbuf = NULL;
    int tbuf[32] = { 0 };
 
    rbuf = calloc(MAX_SIZE, sizeof(int *));
    for (i = 0; i < MAX_SIZE; i++) {
        rbuf[i] = calloc(k, sizeof(int));
    }
 
    len = 0;
    dfs(k, n, 0, tbuf, 0, rbuf, &len);
 
    *returnSize = len;
    *returnColumnSizes = calloc(len, sizeof(int));
    for (i = 0; i < len; i++) {
        (*returnColumnSizes)[i] = k;
    }
 
    return rbuf;
}