46. 全排列-dfs双百代码

46. 全排列-dfs双百代码

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[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 f1(int n){
    
     int re=1;
     while(n>=1){
    
         re=re*n;
         n--;
     }
     return re;
 }

int re_size;
 void dfs(int *nums,int numsSize,int *r,int now_size,int *t,int **re){
    
      int i;
     if(now_size==numsSize){
    
         re[re_size]=(int *)malloc(sizeof(int )*numsSize);
        
         for(i=0;i<numsSize;i++){
    
               re[re_size][i]=t[i];
            }
            re_size++;
     }
   else{
    
          for(i=0;i<numsSize;i++){
    
         if(r[i]==0){
    
             t[now_size]=nums[i];
             r[i]=1;
             dfs(nums,numsSize,r,now_size+1,t,re);
             r[i]=0;

                     }
                }
     }


 }
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    
  int size=f1(numsSize);
    int **re=(int **)malloc(sizeof(int *)*size);
    *returnColumnSizes=(int *)malloc(sizeof(int)*size);
    

    int *t=(int *)malloc(sizeof(int )*numsSize);
    int r[numsSize];
    int i;
    re_size=0;
     for(i=0;i<size;i++){
    
         (*returnColumnSizes)[i]=numsSize;
     }
    for(i=0;i<numsSize;i++){
    
        r[i]=0;
    }
     dfs(nums,numsSize,r,0,t,re);
     *returnSize=re_size;
     return re;

}