leetcode 46题 c语言

题目描述：

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

示例:

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

解题思路：

这是一个典型的回溯算法的问题，我们可以通过递归的方式实现。我们先固定一个数，再递归求解剩下的数的排列，最后再将固定的数和递归求解的结果合并。

代码实现：

void backtrack(int* nums, int numsSize, int** result, int* returnSize, int index) {
if (index == numsSize) { // 递归结束
result[*returnSize] = (int *)malloc(numsSize * sizeof(int)); // 为result分配空间
memcpy(result[*returnSize], nums, numsSize * sizeof(int)); // 将nums复制到result中
(*returnSize)++; // 返回结果数量自增1
return;
}
for (int i = index; i < numsSize; i++) { // 遍历数组
// 交换元素
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
// 递归
backtrack(nums, numsSize, result, returnSize, index + 1);
// 恢复原数组
temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int count = 1;
for (int i = 2; i <= numsSize; i++) {
count *= i; // 计算排列的总数
}
int** result = (int **)malloc(count * sizeof(int *));
*returnColumnSizes = (int *)malloc(count * sizeof(int));
*returnSize = 0;
backtrack(nums, numsSize, result, returnSize, 0);
for (int i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = numsSize;
}
return result;
}