leetcode 46. 全排列 中等

给定一个不含重复数字的数组 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]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

分析：先给出位置的全排列，再将对应位置的数字存储下来。

/**
 * 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 temp[15],flag[15];
int t_cnt=0;
void getans(int index,int n,int **ans,int *nums)
{
    if(index==n)
    {
        for(int i=0;i<n;++i)
            ans[t_cnt][i]=nums[temp[i]];
        t_cnt++;
        return;
    }
    for(int i=0;i<n;++i)
    {
        if(!flag[i])
        {
            temp[index]=i,flag[i]=1;
            getans(index+1,n,ans,nums);
            flag[i]=0;
        }
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int cnt=1;
    for(int i=2;i<=numsSize;++i)
        cnt*=i;
    int **ans=(int**)malloc(sizeof(int*)*721);
    for(int i=0;i<721;++i)
        ans[i]=(int*)malloc(sizeof(int)*numsSize);
    
    *returnColumnSizes=(int*)malloc(sizeof(int)*721);
    for(int i=0;i<cnt;++i)
        (*returnColumnSizes+i)[0]=numsSize;
    *returnSize=cnt;
    t_cnt=0;
    getans(0,numsSize,ans,nums);

    return ans;
}