力扣第46题“全排列”

题目描述

给定一个没有重复数字的整数数组 nums，返回其所有可能的排列。

示例：

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

解题思路

回溯法：通过递归构建排列，每次选择一个未使用的数字添加到当前排列中。
使用数组标记已选数字：使用一个布尔数组 used 来标记某个元素是否已被使用。
递归和回溯：每次添加一个新的数字到排列中，递归地继续添加直到形成完整排列，再回溯到上一状态尝试其他可能性。

代码实现

下面是详细的代码实现。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct {int** data;       // 存储所有排列结果int* columnSizes; // 每个排列的长度int size;         // 当前排列的数量int capacity;     // 容量
} ResultArray;// 初始化结果数组
ResultArray* createResultArray(int capacity) {ResultArray* result = (ResultArray*)malloc(sizeof(ResultArray));result->data = (int**)malloc(capacity * sizeof(int*));result->columnSizes = (int*)malloc(capacity * sizeof(int));result->size = 0;result->capacity = capacity;return result;
}// 添加排列到结果数组
void addResult(ResultArray* result, int* permutation, int length) {if (result->size >= result->capacity) {result->capacity *= 2;result->data = (int**)realloc(result->data, result->capacity * sizeof(int*));result->columnSizes = (int*)realloc(result->columnSizes, result->capacity * sizeof(int));}result->data[result->size] = (int*)malloc(length * sizeof(int));for (int i = 0; i < length; i++) {result->data[result->size][i] = permutation[i];}result->columnSizes[result->size] = length;result->size++;
}// 递归函数生成排列
void backtrack(int* nums, int numsSize, int* permutation, int level, bool* used, ResultArray* result) {if (level == numsSize) {  // 生成完整排列addResult(result, permutation, numsSize);return;}for (int i = 0; i < numsSize; i++) {if (!used[i]) {  // 选择一个未使用的数字used[i] = true;permutation[level] = nums[i];backtrack(nums, numsSize, permutation, level + 1, used, result);  // 递归used[i] = false;  // 回溯}}
}// 主函数
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {ResultArray* result = createResultArray(100); // 初始化结果数组int* permutation = (int*)malloc(numsSize * sizeof(int));bool* used = (bool*)calloc(numsSize, sizeof(bool));backtrack(nums, numsSize, permutation, 0, used, result);*returnSize = result->size;*returnColumnSizes = result->columnSizes;free(permutation);free(used);return result->data;
}// 测试代码
int main() {int nums[] = {1, 2, 3};int numsSize = sizeof(nums) / sizeof(nums[0]);int returnSize;int* returnColumnSizes;int** result = permute(nums, numsSize, &returnSize, &returnColumnSizes);printf("所有排列结果:\n");for (int i = 0; i < returnSize; i++) {printf("[");for (int j = 0; j < returnColumnSizes[i]; j++) {printf("%d", result[i][j]);if (j < returnColumnSizes[i] - 1) printf(", ");}printf("]\n");free(result[i]);}free(result);free(returnColumnSizes);return 0;
}

代码解析

定义结果数组结构体：
- ResultArray 结构体用于存储所有排列及其相关信息，包含每个排列的长度和排列结果的指针。
初始化结果数组：
```
ResultArray* createResultArray(int capacity)
```
用于初始化 ResultArray 结构体，分配初始容量为 100 的空间。
添加排列到结果数组：
```
void addResult(ResultArray* result, int* permutation, int length)
```
将生成的排列添加到 ResultArray 中，当数组满时进行扩容。
回溯函数 backtrack：
```
void backtrack(int* nums, int numsSize, int* permutation, int level, bool* used, ResultArray* result)
```
- 使用 level 表示当前排列的层级。
- used 数组用于标记哪些数字已被使用，避免重复。
- 每次递归生成完整排列时，调用 addResult 保存结果。
主函数 permute：
```
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
```
- 初始化 ResultArray 结构体，调用 backtrack 函数生成排列。
- 设置 returnSize 和 returnColumnSizes，用于返回结果。