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)*方法。
代码的整体逻辑是通过递归的方式，生成所有可能的排列组合。每次递归将一个未使用的数字添加到当前排列中，直到排列长度等于原数组长度时，将该排列加入结果集中。

拆解分析

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

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;
}