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 中的所有整数互不相同

代码

完整代码

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void dfs(int* nums, bool* isUsed, int** answer, int ansIndexNow, int numsSize, int* thisTurnArr, int* resRowIndex)
{
    if (numsSize == ansIndexNow)
    {
        answer[*resRowIndex] = (int*)calloc(numsSize, sizeof(int));
        for (int i = 0; i < numsSize; i++)
        {
            answer[*resRowIndex][i] = thisTurnArr[i];
        }
        (*resRowIndex)++;
        return;
    }
    for (int i = 0; i < numsSize; i++)
    {
        if (!isUsed[i])
        {
            thisTurnArr[ansIndexNow] = nums[i];
            printf("thisturn[%d] = %d\n", ansIndexNow , nums[i]);
            isUsed[i] = true;
            dfs(nums, isUsed, answer, ansIndexNow + 1, numsSize, thisTurnArr, resRowIndex);
            isUsed[i] = false;
        }
    }
    return;
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    *returnSize = 1;
    for (int i = 1; i <= numsSize; i++)
    {
        (*returnSize) *= i; // 计算排列数
    }
    
    int** res = (int**)calloc(*returnSize, sizeof(int*));
    *returnColumnSizes = (int*)calloc(*returnSize, sizeof(int));
    for (int i = 0; i < *returnSize; i++)
    {
        (*returnColumnSizes)[i] = numsSize;
    }

    bool* isUsed = (bool*)calloc(numsSize, sizeof(bool));
    int* thisTurnArr = (int*)calloc(numsSize, sizeof(int));
    int resRowIndex = 0;
    dfs(nums, isUsed, res, 0, numsSize, thisTurnArr, &resRowIndex);
    
    free(isUsed);
    free(thisTurnArr);
    
    return res;
}

思路分析

这套代码用了*深度优先搜索(DFS)*方法。
代码的整体逻辑是通过递归的方式，生成所有可能的排列组合。每次递归将一个未使用的数字添加到当前排列中，直到排列长度等于原数组长度时，将该排列加入结果集中。

拆解分析

1. dfs函数

void dfs(int* nums, bool* isUsed, int** answer, int ansIndexNow, int numsSize, int* thisTurnArr, int* resRowIndex)
{
    if (numsSize == ansIndexNow)
    {
        answer[*resRowIndex] = (int*)calloc(numsSize, sizeof(int));
        for (int i = 0; i < numsSize; i++)
        {
            answer[*resRowIndex][i] = thisTurnArr[i];
        }
        (*resRowIndex)++;
        return;
    }
    for (int i = 0; i < numsSize; i++)
    {
        if (!isUsed[i])
        {
            thisTurnArr[ansIndexNow] = nums[i];
            printf("thisturn[%d] = %d\n", ansIndexNow , nums[i]);
            isUsed[i] = true;
            dfs(nums, isUsed, answer, ansIndexNow + 1, numsSize, thisTurnArr, resRowIndex);
            isUsed[i] = false;
        }
    }
    return;
}

dfs函数的解析：
该函数用于生成当前排列组合。通过递归，将每个未使用的数字添加到当前排列中，直到当前排列长度等于原数组长度，将该排列加入结果集中。

2. permute函数

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    *returnSize = 1;
    for (int i = 1; i <= numsSize; i++)
    {
        (*returnSize) *= i; // 计算排列数
    }
    
    int** res = (int**)calloc(*returnSize, sizeof(int*));
    *returnColumnSizes = (int*)calloc(*returnSize, sizeof(int));
    for (int i = 0; i < *returnSize; i++)
    {
        (*returnColumnSizes)[i] = numsSize;
    }

    bool* isUsed = (bool*)calloc(numsSize, sizeof(bool));
    int* thisTurnArr = (int*)calloc(numsSize, sizeof(int));
    int resRowIndex = 0;
    dfs(nums, isUsed, res, 0, numsSize, thisTurnArr, &resRowIndex);
    
    free(isUsed);
    free(thisTurnArr);
    
    return res;
}

permute函数的解析：
该函数用于初始化和调用dfs函数。首先计算排列数目，分配内存，初始化标志数组和当前排列数组，最后调用dfs函数生成所有排列组合。

复杂度分析

• 时间复杂度：O(n * n!)，其中n是数组长度。每个排列的生成需要O(n)的时间，总共有n!个排列。
• 空间复杂度：O(n * n!)，需要存储所有的排列组合和递归调用栈。

结果