含有重复元素集合的全排列
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,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().
*/
void q_sort(int *nums,int low ,int high){
int l=low,h=high;
if(low<high){
int pivat=nums[low];
while(low<high){
while(low<high&&nums[high]>=pivat){
high--;
}
nums[low]=nums[high];
while(low<high&&nums[low]<=pivat){
low++;
}
nums[high]=nums[low];
}
nums[low]=pivat;
q_sort(nums,l,low-1);
q_sort(nums,low+1,h);
}
}
void dfs(int *r,int *nums,int numsSize,int n,int *a,int cun,int* returnSize,int** returnColumnSizes,int **res){
int i;
//printf("n%d",n);
a[n]=cun;
if(n==numsSize-1){
res[*returnSize]=(int *)malloc(sizeof(int)*numsSize);
(*returnColumnSizes)[*returnSize] = numsSize;
for(i=0;i<numsSize;i++){
res[*returnSize][i]=a[i];
/// printf("%d ",res[*returnSize][i]);
}
(*returnSize)++;
printf("cun %d --",cun);
}
else{
printf("cun %d ",cun);
}
for(i=0;i<numsSize;i++){
if(i>=1){
// printf("i%d",i);
if(r[i]==0){
if(nums[i]!=nums[i-1]){
r[i]=1;
dfs(r,nums,numsSize,n+1,a,nums[i],returnSize,returnColumnSizes,res);
r[i]=0;
}
if(nums[i]==nums[i-1]&&r[i-1]==1){
r[i]=1;
dfs(r,nums,numsSize,n+1,a,nums[i],returnSize,returnColumnSizes,res);
r[i]=0;
}
}
}
else{
if(r[i]==0){
// printf("%d ",nums[i]);
r[i]=1;
dfs(r,nums,numsSize,n+1,a,nums[i],returnSize,returnColumnSizes,res);
r[i]=0;
}
}
}
// }
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int *r=(int *)malloc(sizeof(int)*numsSize);
int *a=(int *)malloc(sizeof(int)*numsSize);
*returnSize=0;
int**res = (int**)malloc(sizeof(int*) * 100001);
*returnColumnSizes=(int *)malloc(sizeof(int *)*1000);
int i,j;
q_sort(nums,0,numsSize-1);
for(i=0;i<numsSize;i++){
r[i]=0;
printf("%d ",nums[i]);
}
for(i=0;i<numsSize;i++){
if(i>=1){
//printf("df-- ");
// printf("%d %d ",r[i],r[i-1]);
//printf("df123");
if(r[i]==0&&nums[i]!=nums[i-1]){
r[i]=1;
dfs(r,nums,numsSize,0,a,nums[i],returnSize,returnColumnSizes,res);
r[i]=0;
// printf("df");
}
}
else{
if(r[i]==0){
r[i]=1;
dfs(r,nums,numsSize,0,a,nums[i],returnSize,returnColumnSizes,res);
r[i]=0;
}
}
}
printf("%d ",*returnSize);
return res;
}
