LeetCode 第46题：全排列

题目描述

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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 中的所有整数 互不相同

解题思路

回溯算法

这是一道经典的回溯算法题目。回溯算法的核心思想是：从一个空的排列开始，每次选择一个还未使用过的数字加入当前排列，直到得到一个完整的排列。

关键点：

1. 使用一个标记数组记录每个数字是否已被使用
2. 使用递归函数实现回溯过程
3. 当排列长度等于原数组长度时，得到一个完整排列
4. 需要在回溯时撤销选择，恢复现场

具体步骤：

1. 初始化结果列表和标记数组
2. 定义回溯函数，包含当前排列和使用标记
3. 遍历数组，选择未使用的数字
4. 标记选中的数字，继续递归
5. 递归返回后撤销标记，尝试下一个数字

图解思路

算法步骤分析表

步骤	当前排列	可选数字	操作	说明
初始	[]	[1,2,3]	开始	空排列
选择1	[1]	[2,3]	选择1	第一个数字
选择2	[1,2]	[3]	选择2	第二个数字
完成	[1,2,3]	[]	记录	得到一个排列
回溯	[1]	[2,3]	撤销2	回到选择1后

状态/情况分析表

情况	输入	输出	说明
单个数字	[1]	[[1]]	只有一种排列
两个数字	[1,2]	[[1,2],[2,1]]	两种排列
三个数字	[1,2,3]	6种排列	完整示例

代码实现

C# 实现

public class Solution {
    private IList<IList<int>> result = new List<IList<int>>();
    private bool[] used;
    
    public IList<IList<int>> Permute(int[] nums) {
        used = new bool[nums.Length];
        Backtrack(nums, new List<int>());
        return result;
    }
    
    private void Backtrack(int[] nums, List<int> current) {
        // 当前排列完成
        if (current.Count == nums.Length) {
            result.Add(new List<int>(current));
            return;
        }
        
        // 尝试每个可能的数字
        for (int i = 0; i < nums.Length; i++) {
            if (used[i]) continue;
            
            // 做选择
            used[i] = true;
            current.Add(nums[i]);
            
            // 继续递归
            Backtrack(nums, current);
            
            // 撤销选择
            current.RemoveAt(current.Count - 1);
            used[i] = false;
        }
    }
}

执行结果

• 执行用时：152 ms
• 内存消耗：42.5 MB

代码亮点

1. 🎯 使用回溯算法的经典实现
2. 💡 通过标记数组避免重复使用数字
3. 🔍 递归函数结构清晰，易于理解
4. 🎨 状态恢复确保回溯的正确性

常见错误分析

1. 🚫 忘记标记数字的使用状态
2. 🚫 没有正确恢复现场（撤销选择）
3. 🚫 递归终止条件写错
4. 🚫 结果列表忘记深拷贝

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
回溯法	O(n!)	O(n)	直观易懂	复杂度高
字典序法	O(n!)	O(1)	空间优化	不易理解
递归交换	O(n!)	O(n)	代码简洁	改变原数组

相关题目

• 全排列 II - 中等
• 下一个排列 - 中等
• 组合 - 中等