Steward

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

程式語言 - LeetCode - C - 47. Permutations II

---

題目：


解答：

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;
        }

        if ((i > 0) && (nums[i] == nums[i - 1]) && !used[i - 1]) {
            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;
    }
}

int mysort(const void *a, const void *b)
{
    return (*(const int *)a) - (*(const int *)b);
}

/**
 * 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** permuteUnique(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));

    qsort(nums, numsSize, sizeof(int), mysort);
    dfs(nums, numsSize, used, t_cnt, 0, r, returnSize, returnColumnSizes);
 
    return r;
}