Steward

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

程式語言 - LeetCode - C - 40. Combination Sum II

---

題目：


解答：

int mysort(const void *a, const void *b)
{
    return (*(const int *)a) - (*(const int *)b);
}
 
void dfs(
    int* candidates,
    int candidatesSize,
    int target,
    int start,
    int* t_buf,
    int t_cnt,
    int** r_buf,
    int* returnSize,
    int** returnColumnSizes)
{
    int i = 0;
 
    if (target == 0) {
        int pos = *returnSize;
 
        (*returnSize) += 1;
        (*returnColumnSizes)[pos] = t_cnt;
 
        r_buf[pos] = calloc(t_cnt, sizeof(int));
        memcpy(r_buf[pos], t_buf, sizeof(int) * t_cnt);
 
        return;
    }
 
    for (i = start; i < candidatesSize; i++) {
        if ((i > start) && (candidates[i] == candidates[i - 1])) {
            continue;
        }

        if (candidates[i] > target) {
            break;
        }
 
        t_buf[t_cnt] = candidates[i];
        t_cnt += 1;
 
        dfs(
            candidates,
            candidatesSize,
            target - candidates[i],
            i + 1,
            t_buf,
            t_cnt,
            r_buf,
            returnSize,
            returnColumnSizes
        );
 
        t_cnt -= 1;
    }
}

/**
 * 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** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
{
    #define MAX_SIZE 5000
 
    int **r = calloc(MAX_SIZE, sizeof(int));
    int *t = calloc(MAX_SIZE, sizeof(int));
 
    *returnSize = 0;
    *returnColumnSizes = calloc(MAX_SIZE, sizeof(int));
    qsort(candidates, candidatesSize, sizeof(int), mysort);
 
    dfs(
        candidates,
        candidatesSize,
        target,
        0,
        t,
        0,
        r,
        returnSize,
        returnColumnSizes
    );
 
    return r;
}