Steward

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

程式語言 - LeetCode - C - 46. Permutations

---

題目：


解答：

void dfs(
    int* nums,
    int numsSize,
    int* used,
    int* t_buf,
    int t_cnt,
    int** r_buf,
    int* r_cnt,
    int** returnColumnSizes)
{
    int i = 0;

    if (t_cnt >= numsSize) {
        int pos = (*r_cnt)++;

        (*returnColumnSizes)[pos] = numsSize;
        r_buf[pos] = calloc(numsSize, sizeof(int));
        memcpy(r_buf[pos], t_buf, numsSize * sizeof(int));
        return;
    }

    for (i = 0; i < numsSize; i++) {
        if (used[i]) {
            continue;
        }

        used[i] = 1;
        t_buf[t_cnt++] = nums[i];

        dfs(nums, numsSize, used, t_buf, t_cnt, r_buf, r_cnt, returnColumnSizes);

        used[i] = 0;
        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** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    #define MAX_SIZE 5000

    int **r = calloc(MAX_SIZE, sizeof(int **));
    int *t_cnt = calloc(MAX_SIZE, sizeof(int));
    int *used = calloc(MAX_SIZE, sizeof(int));

    *returnSize = 0;
    *returnColumnSizes = calloc(MAX_SIZE, sizeof(int));
    dfs(nums, numsSize, used, t_cnt, 0, r, returnSize, returnColumnSizes);

    return r;
}