DeepSeek LeetCode 47. 全排列 II C语言实现

以下是 LeetCode 47. 全排列 II 的 C 语言实现，采用回溯 + 排序去重的方法：

#include <stdlib.h>
#include <string.h>

// 比较函数，用于 qsort
int cmp(const void* a, const void* b) {
return (*(int*)a – *(int*)b);
}

// 回溯函数
void backtrack(int* nums, int numsSize, int* used, int* path, int depth,
int*** result, int* returnSize, int** returnColumnSizes, int* capacity) {
if (depth == numsSize) {
// 复制当前排列
int* perm = (int*)malloc(numsSize * sizeof(int));
memcpy(perm, path, numsSize * sizeof(int));

// 动态扩容结果数组
if (*returnSize >= *capacity) {
*capacity = (*capacity == 0) ? 10 : (*capacity) * 2;
*result = (int**)realloc(*result, (*capacity) * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, (*capacity) * sizeof(int));
}
(*result)[*returnSize] = perm;
(*returnColumnSizes)[*returnSize] = numsSize;
(*returnSize)++;
return;
}

for (int i = 0; i < numsSize; i++) {
if (used[i]) continue;
// 去重：若当前元素与前一个相同，且前一个未被使用，则跳过
if (i > 0 && nums[i] == nums[i–1] && !used[i–1]) continue;

used[i] = 1;
path[depth] = nums[i];
backtrack(nums, numsSize, used, path, depth + 1, result, returnSize, returnColumnSizes, capacity);
used[i] = 0;
}
}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
// 先排序，使相同元素相邻
qsort(nums, numsSize, sizeof(int), cmp);

int* used = (int*)calloc(numsSize, sizeof(int));
int* path = (int*)malloc(numsSize * sizeof(int));

int capacity = 0;
int** result = NULL;
int* colSizes = NULL;
*returnSize = 0;

backtrack(nums, numsSize, used, path, 0, &result, returnSize, &colSizes, &capacity);

// 释放辅助数组
free(used);
free(path);

*returnColumnSizes = colSizes;
return result;
}

思路说明

· 排序：先对数组排序，让相同的数字相邻，便于后续去重。
· 回溯：使用递归枚举所有排列，used 数组标记元素是否已在当前路径中。
· 去重核心：在遍历时，若 nums[i] == nums[i-1] 且 used[i-1] == false，说明前一个相同元素刚被撤销选择（即同一层递归中已经尝试过该值），跳过当前元素可避免重复排列。
· 动态内存管理：结果数组和列大小数组采用动态扩容（初始容量为0，首次分配10，之后倍增），确保能容纳所有排列。

复杂度分析

· 时间复杂度：O(n × n!)，最坏情况下需要生成所有排列，排序 O(n log n)，剪枝减少了实际计算量。
· 空间复杂度：O(n)，递归栈深度为 n，used 和 path 各占 O(n)，结果存储不计入额外空间。

此实现符合 C 语言的内存管理规范，调用方需负责释放返回的二维数组和列大小数组。