/**

 * 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().

 */

void back(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int *path,int *pathSize,int **result,int *visited){

    if(numsSize==*pathSize){

        result[*returnSize] = (int *)malloc(sizeof(int)*numsSize);

        memcpy(result[*returnSize],path,sizeof(int)*numsSize);

        (*returnColumnSizes)[*returnSize] = numsSize;

        (*returnSize)++;

        return;

    }

    for(int i=0;i<numsSize;i++){

        if(visited[i]==1||(i>0&&nums[i-1]==nums[i]&&visited[i-1]==0)){

            continue;

        }

        path[*pathSize] = nums[i];

        visited[i] = 1;

        (*pathSize)++;

        back(nums,numsSize,returnSize,returnColumnSizes,path,pathSize,result,visited);

        visited[i] = 0;

        (*pathSize)--;

    }

}

void QuickSort1(int* a, int left, int right)

{

    if (left >= right)

    {

        return;

    }

    int begin = left, end = right;

    //三数取中

    //int midIndex = GetThreeMid(a,begin,end);

    //Swap(&a[begin],&a[midIndex]);

    int pivot = begin;

    int key = a[begin];

    while (begin < end)

    {

        //右边找小的，如果不是小于key,继续

        while (begin < end && a[end] >= key)

        {

            end--;

        }

        //找到比key小的，把它放在坑里，换新坑

        a[pivot] = a[end];

        pivot = end;

        //左边找大的，如果不是大于key,继续

        while (begin < end && a[begin] <= key)

        {

            begin++;

        }

        //找到比key大的，把它放在坑里，换新坑

        a[pivot] = a[begin];

        pivot = begin;

    }

    a[pivot] = key;//bengin 与 end 相遇，相遇的位置一定是一个坑

    QuickSort1(a, left, pivot - 1);

    QuickSort1(a, pivot + 1, right);

}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    QuickSort1(nums,0,numsSize-1);

    *returnSize = 0;

    *returnColumnSizes = (int *)malloc(sizeof(int)*100001);

    int *path = (int *)malloc(sizeof(int)*numsSize);

    int **result = (int **)malloc(sizeof(int *)*100001);

    int *visited = (int *)calloc(numsSize,sizeof(int));

    int *pathSize = (int *)calloc(1,sizeof(int));

    back(nums,numsSize,returnSize,returnColumnSizes,path,pathSize,result,visited);

    return result;

}

class Solution {

public:

    vector<int> path;

    vector<vector<int>> result;

    void back(vector<int>& nums,vector<bool>& visited){

        if(path.size()==nums.size()){

            result.push_back(path);

            return;

        }

        for(int i=0;i<nums.size();i++){

            if(visited[i]||(i>0 && nums[i-1]==nums[i]&&visited[i-1]==false)){

                continue;

            }

            path.push_back(nums[i]);

            visited[i] = true;

            back(nums,visited);

            visited[i] = false;

            path.pop_back();

        }

    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(),nums.end());

        vector<bool> visited(nums.size(),false);

        back(nums,visited);

        return result;

    }

};

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    LinkedList<Integer> path = new LinkedList<>();

    void back(int[] nums,boolean[] visited){

        if(nums.length == path.size()){

            result.add(new ArrayList<>(path));

            return;

        }

        for(int i=0;i<nums.length;i++){

            if(visited[i]){continue;}

            if(i>0&&nums[i-1]==nums[i]&&visited[i]==false&&visited[i-1]==false){

                continue;

            }

                visited[i] = true;

                path.add(nums[i]);

                back(nums,visited);

                path.removeLast();

                visited[i] = false;

        }

    }

    public List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);

        boolean visited[] = new boolean[nums.length];

        Arrays.fill(visited,false);

        back(nums,visited);

        return result;

    }

}

class Solution(object):

    def __init__(self):

        self.path = []

        self.result = []

    def back(self,nums,visited):

        if len(nums)==len(self.path):

            self.result.append(self.path[:])

            return

        for i in range(len(nums)):

            if visited[i]==True:

                continue

            if i>0 and nums[i-1]==nums[i] and visited[i-1]==False:

                continue

            visited[i]=True

            self.path.append(nums[i])

            self.back(nums,visited)

            self.path.pop()

            visited[i]=False

    def permuteUnique(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        nums.sort()

        visited = [False]*len(nums)

        self.back(nums,visited)

        return self.result