1.核心思想

dfs+回溯+去重

3. 分析流程

dfs中最重要的是搜索顺序，做到不重不漏！！！

至于本题搜索顺序：依次枚举排列的每个位置所有可能取值
然后对于去重问题首先需要排序，目的是把相同的数排序到一起
比如：
对于 1122233
对于第1个位置：不考虑去重那么所有的可能情况是1（第一个1），1（第2个1），2（第1个2），2（第二个2），2（第三个2），3（第1个3），3（第2个3）
去重要怎么做？才能达到第一个位置取值所有情况为1，2，3
做法：利用双指针，从前往后，找到第一个不重复的数字。第一次扫描到1，ok一个可能取值，然后跳过之后的所有1；继续扫描到2，ok又得到一个可能取值，然后跳过之后的所有2，以此类推

题目描述举例

给定一个可包含重复数字的序列，返回所有不重复的全排列。

样例

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

C 代码

#define N 100010

int ** ans;
int cnt;
int *path;
int idx;
int vst[N];
int *col;

int cmp(const void* a, const void* b){
    int x = *(int*)a;
    int y = *(int*)b;
    if(x <= y){
        return -1;
    }else {
        return 1;
    }
}

void dfs(int* nums, int u, int L)
{
    if(u == L){
        col[cnt] = L;
        memcpy(ans[cnt++], path, sizeof(int) * L);
        return ;
    }

    //枚举当前位置所有的可能性
    for(int i = 0; i < L; ){
        //找到某个数T第一次使用
        if(vst[i] == false){
            vst[i] = true;
            path[idx++] = nums[i];
            dfs(nums, u + 1, L);

            idx--;
            vst[i] = false;

            // 跳过T之后和T相同的数字
            int j = i + 1;
            while(j <= L - 1 && nums[j] == nums[j - 1]) j++;
            i = j;
        } else {
            i ++;
        }
    }
}

/**
 * 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){
    if(nums == NULL || numsSize <= 0){
        *returnSize = 0;
        return NULL;
    }
    //1. reset
    cnt = 0;
    idx = 0;
    memset(vst, 0, sizeof(int) * N);

    //2. sort
    qsort(nums, numsSize, sizeof(int), cmp);

    //3. prepare
    ans = (int**)malloc(sizeof(int*) * N);
    for(int i = 0; i < N; i++){
        ans[i] = (int*)malloc(sizeof(int) * numsSize);
    }
    col = (int*)malloc(sizeof(int) * N);
    path = (int*)malloc(sizeof(int) * numsSize);

    //4. dfs
    dfs(nums, 0, numsSize);

    //5. result
    *returnSize = cnt;
    *returnColumnSizes = col;
    return ans;
}