全排列

问题描述

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

示例 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. 递归终止条件

• 正确识别何时完成一个完整的排列
• 在适当的时机保存结果并返回

解法分析

方法一：回溯法（推荐）

核心思想：

• 使用递归的方式，每次选择一个未使用的元素加入当前排列
• 当排列长度等于原数组长度时，保存当前排列
• 回溯时移除最后添加的元素，尝试其他可能性

算法步骤：

1. 创建一个布尔数组记录元素是否已被使用
2. 递归函数中遍历所有元素
3. 选择未使用的元素加入当前路径
4. 标记该元素为已使用，继续递归
5. 递归返回后，移除该元素并标记为未使用（回溯）

方法二：交换法

核心思想：

• 通过交换数组中的元素来生成不同的排列
• 固定前面的元素，对后面的元素进行全排列

方法三：迭代法

核心思想：

• 从一个元素开始，逐步插入新元素生成更长的排列
• 对于每个新元素，将其插入到现有排列的所有可能位置

方法四：字典序法

核心思想：

• 按字典序生成下一个排列
• 重复此过程直到生成所有排列

详细代码实现

Java实现（回溯法）

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        
        backtrack(nums, current, used, result);
        return result;
    }
    
    private void backtrack(int[] nums, List<Integer> current, 
                          boolean[] used, List<List<Integer>> result) {
        // 递归终止条件：当前排列长度等于原数组长度
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // 注意：需要创建新的ArrayList
            return;
        }
        
        // 遍历所有元素
        for (int i = 0; i < nums.length; i++) {
            // 跳过已使用的元素
            if (used[i]) {
                continue;
            }
            
            // 选择当前元素
            current.add(nums[i]);
            used[i] = true;
            
            // 递归处理剩余元素
            backtrack(nums, current, used, result);
            
            // 回溯：撤销选择
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

Python实现（回溯法）

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        current = []
        used = [False] * len(nums)
        
        def backtrack():
            # 递归终止条件
            if len(current) == len(nums):
                result.append(current[:])  # 注意：需要创建副本
                return
            
            # 遍历所有元素
            for i in range(len(nums)):
                # 跳过已使用的元素
                if used[i]:
                    continue
                
                # 选择当前元素
                current.append(nums[i])
                used[i] = True
                
                # 递归处理
                backtrack()
                
                # 回溯：撤销选择
                current.pop()
                used[i] = False
        
        backtrack()
        return result

Python实现（交换法）

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start):
            # 递归终止条件
            if start == len(nums):
                result.append(nums[:])
                return
            
            # 尝试将每个元素放在start位置
            for i in range(start, len(nums)):
                # 交换元素
                nums[start], nums[i] = nums[i], nums[start]
                
                # 递归处理剩余位置
                backtrack(start + 1)
                
                # 回溯：恢复交换
                nums[start], nums[i] = nums[i], nums[start]
        
        backtrack(0)
        return result

复杂度分析

时间复杂度

• 回溯法： O(n! × n)
  • 总共有 n! 个排列
  • 每个排列需要 O(n) 时间来构建和复制
• 交换法： O(n! × n)
  • 同样需要生成 n! 个排列
  • 每次交换和恢复的操作是 O(1)，但复制结果需要 O(n)

空间复杂度

• 回溯法： O(n)
  • 递归调用栈深度为 n
  • used 数组占用 O(n) 空间
  • current 数组最大长度为 n
• 交换法： O(n)
  • 递归调用栈深度为 n
  • 原地修改数组，不需要额外的 used 数组

注意： 以上复杂度分析不包括存储最终结果的空间，如果包括结果存储，空间复杂度为 O(n! × n)。

边界情况处理

1. 空数组

if not nums:
    return [[]]

2. 单元素数组

if len(nums) == 1:
    return [nums[:]]

3. 两元素数组

• 应该返回 [[a,b], [b,a]]
• 验证算法的基本正确性

相关变种问题

1. 全排列 II（包含重复元素）

LeetCode 47

• 需要在回溯过程中跳过重复元素
• 先对数组排序，然后在递归中跳过相同的元素

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    nums.sort()  # 排序以便跳过重复元素
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            # 跳过重复元素：如果当前元素与前一个元素相同，且前一个元素未被使用
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            
            current.append(nums[i])
            used[i] = True
            backtrack(current)
            current.pop()
            used[i] = False
    
    backtrack([])
    return result

2. 下一个排列

LeetCode 31

• 找到给定排列的下一个字典序更大的排列
• 如果不存在，则返回最小的排列

3. 第k个排列

LeetCode 60

• 直接计算第k个排列，而不需要生成所有排列
• 使用数学方法和阶乘来计算

4. 字符串的排列

LeetCode 567

• 判断一个字符串的排列是否是另一个字符串的子串

性能优化技巧

1. 早期剪枝

# 如果剩余元素数量不足以完成排列，提前返回
if len(current) + (len(nums) - i) < len(nums):
    break

2. 内存优化

• 使用交换法可以减少额外的 used 数组
• 在可能的情况下，重用数据结构

3. 迭代器模式

def permute_generator(nums):
    """生成器版本，节省内存"""
    if len(nums) <= 1:
        yield nums[:]
        return
    
    for i in range(len(nums)):
        for perm in permute_generator(nums[:i] + nums[i+1:]):
            yield [nums[i]] + perm

4. 位运算优化（适用于小规模数据）

def permute_bitmask(nums):
    """使用位掩码记录使用状态"""
    n = len(nums)
    result = []
    
    def backtrack(current, mask):
        if len(current) == n:
            result.append(current[:])
            return
        
        for i in range(n):
            if mask & (1 << i):  # 检查第i位是否为1
                continue
            
            current.append(nums[i])
            backtrack(current, mask | (1 << i))  # 设置第i位为1
            current.pop()
    
    backtrack([], 0)
    return result

实际应用场景

1. 密码生成

• 生成包含特定字符集的所有可能密码
• 用于密码强度测试和暴力破解分析

2. 任务调度

• 生成所有可能的任务执行顺序
• 找到最优的调度方案

3. 游戏AI

• 棋类游戏中生成所有可能的移动序列
• 路径规划和策略分析

4. 组合优化

• 旅行商问题（TSP）的暴力解法
• 资源分配问题

5. 测试用例生成

• 自动化测试中生成所有可能的输入组合
• 边界测试和压力测试

6. 数据分析

• 生成数据的所有可能排列进行统计分析
• A/B测试中的实验设计

常见错误与调试

1. 浅拷贝问题

错误代码：

result.append(current)  # 错误：所有结果都指向同一个列表

正确代码：

result.append(current[:])  # 正确：创建副本
# 或者
result.append(list(current))

2. 回溯不完整

错误代码：

current.append(nums[i])
used[i] = True
backtrack()
# 忘记回溯操作

正确代码：

current.append(nums[i])
used[i] = True
backtrack()
current.pop()      # 必须回溯
used[i] = False    # 必须回溯

3. 递归终止条件错误

错误代码：

if len(current) > len(nums):  # 错误：应该是等于
    return

正确代码：

if len(current) == len(nums):  # 正确：等于时保存结果
    result.append(current[:])
    return

4. 调试技巧

def backtrack(current, used, depth=0):
    # 添加调试信息
    print("  " * depth + f"Current: {current}, Used: {used}")
    
    if len(current) == len(nums):
        print("  " * depth + f"Found permutation: {current}")
        result.append(current[:])
        return
    
    for i in range(len(nums)):
        if used[i]:
            continue
        
        print("  " * depth + f"Trying: {nums[i]}")
        current.append(nums[i])
        used[i] = True
        backtrack(current, used, depth + 1)
        current.pop()
        used[i] = False
        print("  " * depth + f"Backtracked from: {nums[i]}")

面试要点总结

1. 常见面试问题

Q: 为什么选择回溯法？ A: 回溯法是解决排列组合问题的经典方法，具有以下优势：

• 思路清晰，易于理解和实现
• 可以处理各种约束条件
• 空间复杂度相对较低
• 可以很容易地扩展到相关问题

Q: 如何优化算法性能？ A: 主要优化策略包括：

• 早期剪枝：在不可能产生有效解的分支上提前返回
• 使用位运算：对于小规模数据，用位掩码替代布尔数组
• 迭代器模式：对于大规模数据，使用生成器节省内存
• 交换法：减少额外的空间开销

Q: 时间复杂度为什么是 O(n! × n)？ A:

• n! 表示总共有 n! 个排列需要生成
• 每个排列的生成和复制需要 O(n) 时间
• 因此总时间复杂度为 O(n! × n)

Q: 如何处理重复元素？ A:

• 首先对数组进行排序
• 在递归过程中跳过重复元素
• 使用条件：nums[i] == nums[i-1] and not used[i-1]

2. 代码实现要点

• 正确处理递归终止条件
• 确保完整的回溯操作
• 注意结果保存时的深拷贝
• 合理选择数据结构（数组 vs 列表）

3. 扩展思考

• 如何将算法扩展到字符串排列？
• 如何处理更复杂的约束条件？
• 在实际项目中如何选择合适的算法？

4. 最佳回答策略

1. 先说思路：简要说明回溯法的核心思想
2. 画图解释：用简单例子演示递归过程
3. 写出代码：先写主要逻辑，再完善细节
4. 分析复杂度：说明时间和空间复杂度
5. 讨论优化：提及可能的优化方案
6. 举例测试：用简单例子验证代码正确性

总结

全排列问题是回溯算法的经典应用，掌握这个问题对理解递归和回溯思想非常重要。关键要点包括：

核心要点

1. 回溯法是最常用和最直观的解法
2. 正确处理递归终止条件和回溯操作
3. 注意结果保存时的深拷贝问题
4. 理解时间复杂度 O(n! × n) 的来源

学习建议

1. 从简单例子开始：先理解 [1,2] 的排列过程
2. 画出递归树：可视化递归调用过程
3. 手动跟踪代码：逐步执行理解每个步骤
4. 练习相关变种：全排列II、下一个排列等
5. 关注实现细节：深拷贝、回溯完整性等

扩展学习

• 组合问题（Combinations）
• 子集问题（Subsets）
• N皇后问题
• 数独求解
• 图的遍历算法

通过深入理解全排列问题，可以为解决更复杂的回溯和递归问题打下坚实的基础。