每日一题——没有重复项数字的全排列

没有重复项数字的全排列

- 示例
- 题解
- - 思路
  - 代码实现
  - 代码解释
  - 时间复杂度与空间复杂度分析
- 讨论

建议先看视频讲解

## 题目

给出一组数字，返回该组数字的所有排列。例如，给定输入 [1,2,3]，其所有排列如下：

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

排列是按字典序输出的。

数据范围：

数字个数 $\leq 6$

要求：

时间复杂度： $O (n!)$
空间复杂度： $O (n!)$

示例

示例 1：

输入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：

[1]

返回值：

[[1]]

题解

该问题可以通过回溯算法解决。回溯算法的核心思想是通过递归遍历所有可能的排列，同时通过标记来避免重复选取相同的数字。

思路

使用回溯方法生成所有排列。
在每一步选择一个数字加入当前排列，并且递归处理剩下的数字。
一旦一个排列生成完成，将其保存到结果列表中。
使用一个used数组来标记哪些元素已经在当前排列中被使用过，避免重复。

代码实现

#include <stdio.h>
#include <stdlib.h>// 回溯函数：生成全排列
void backtrack(int* num, int numLen, int** result, int* returnSize,int* returnColumnSizes, int* current, int currentLen, int* used) {// num: 输入的数字数组// numLen: 数组的长度// result: 用于存储所有排列的二维数组// returnSize: 当前已生成的排列数量// returnColumnSizes: 用于存储每个排列的列大小// current: 当前正在构建的排列// currentLen: 当前排列的长度// used: 标记数组，记录哪些元素已经被使用// 如果当前排列长度等于数字长度，说明一个排列已生成if (currentLen == numLen) {// 为当前排列分配内存result[*returnSize] = (int*)malloc(sizeof(int) * numLen);// 将当前排列复制到结果数组中for (int i = 0; i < numLen; i++) {result[*returnSize][i] = current[i];}// 设置当前排列的列大小returnColumnSizes[*returnSize] = numLen;// 增加返回结果的大小(*returnSize)++;// 递归结束，返回return;}// 遍历每个数字，尝试放入当前排列中for (int i = 0; i < numLen; i++) {// 如果该元素没有被使用if (used[i] == 0) {// 标记该元素已使用used[i] = 1;// 将该元素加入当前排列current[currentLen] = num[i];// 递归调用，继续选择下一个元素backtrack(num, numLen, result, returnSize, returnColumnSizes, current,currentLen + 1, used);// 回溯，撤销选择used[i] = 0;}}
}// permute函数，生成所有排列
int** permute(int* num, int numLen, int* returnSize, int** returnColumnSizes) {// num: 输入的数字数组// numLen: 数组的长度// returnSize: 当前已生成的排列数量// returnColumnSizes: 用于存储每个排列的列大小// 预分配空间，最多有10000个排列int** result = (int**)malloc(sizeof(int*) * 10000);// 预分配列大小空间*returnColumnSizes = (int*)malloc(sizeof(int) * 10000);// 初始化返回结果的大小为0*returnSize = 0;// 用于保存当前排列int* current = (int*)malloc(sizeof(int) * numLen);// 用于标记哪些元素已经使用，初始化为0int* used = (int*)calloc(numLen, sizeof(int));// 调用回溯生成排列backtrack(num, numLen, result, returnSize, *returnColumnSizes, current, 0,used);// 释放临时数组free(current);free(used);// 返回结果数组return result;
}