二维数组：全排列

📖 算法简介

全排列是组合数学中的基本概念，也是回溯算法的经典应用。给定一个不含重复数字的数组，返回其所有可能的全排列。这个问题在算法面试中出现频率极高，是理解回溯思想的重要入门题目。

核心思想：通过深度优先搜索，在搜索过程中做选择，到达叶子节点时撤销选择（回溯）。

🎯 问题定义

基本概念

• 排列（Permutation）：从n个不同元素中取出m个元素，按照一定顺序排成一列
• 全排列：取出所有n个元素进行排列，记作P(n,n) = n!
• 组合 vs 排列：组合不考虑顺序，排列考虑顺序

示例说明

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

输入: nums = [0,1]
输出: [[0,1],[1,0]]

输入: nums = [1]
输出: [[1]]

数学基础

• n个不同元素的全排列数量：n!
• 例如：3个元素有3! = 6种排列，4个元素有4! = 24种排列

🧠 算法原理

回溯算法思想

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解，回溯算法会舍弃该候选解，并在上一步进行一些修改后重新尝试。

回溯三要素

1. 选择列表：当前可以做的选择
2. 路径：已经做过的选择
3. 结束条件：到达决策树底层，无法再做选择的条件

递归树分析

以[1,2,3]为例的递归树：

                    []
                 /  |  \
               1/   |2  \3
               /    |    \
           [1]     [2]   [3]
          / \      / \    / \
        2/   \3   1/  \3  1/  \2
        /     \   /    \  /    \
    [1,2]   [1,3] [2,1] [2,3] [3,1] [3,2]
      |       |     |     |     |     |
      3       2     3     1     2     1
      |       |     |     |     |     |
  [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

算法流程

1. 定义递归函数 backtrack(路径, 选择列表)
2. 如果路径长度等于数组长度，添加到结果集
3. 遍历选择列表：
   - 做选择：将元素加入路径
   - 递归调用：backtrack(新路径, 新选择列表)
   - 撤销选择：将元素从路径中移除

💻 代码实现

方法一：标准回溯法（使用used数组）

Java实现

import java.util.*;

public class Permutations {
    /**
     * 生成数组的所有全排列
     * @param nums 输入数组
     * @return 所有排列的列表
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        
        backtrack(nums, path, used, result);
        return result;
    }
    
    /**
     * 回溯函数
     * @param nums 原数组
     * @param path 当前路径
     * @param used 使用状态数组
     * @param result 结果集
     */
    private void backtrack(int[] nums, List<Integer> path, 
                          boolean[] used, List<List<Integer>> result) {
        // 结束条件：路径长度等于数组长度
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // 注意：需要创建新的ArrayList
            return;
        }
        
        // 遍历选择列表
        for (int i = 0; i < nums.length; i++) {
            // 跳过已使用的元素
            if (used[i]) {
                continue;
            }
            
            // 做选择
            path.add(nums[i]);
            used[i] = true;
            
            // 递归
            backtrack(nums, path, used, result);
            
            // 撤销选择（回溯）
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Python实现

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        生成数组的所有全排列
        
        Args:
            nums: 输入数组
        
        Returns:
            所有排列的列表
        """
        result = []
        path = []
        used = [False] * len(nums)
        
        self.backtrack(nums, path, used, result)
        return result
    
    def backtrack(self, nums: List[int], path: List[int], 
                  used: List[bool], result: List[List[int]]) -> None:
        """
        回溯函数
        
        Args:
            nums: 原数组
            path: 当前路径
            used: 使用状态数组
            result: 结果集
        """
        # 结束条件
        if len(path) == len(nums):
            result.append(path[:])  # 注意：需要复制路径
            return
        
        # 遍历选择列表
        for i in range(len(nums)):
            # 跳过已使用的元素
            if used[i]:
                continue
            
            # 做选择
            path.append(nums[i])
            used[i] = True
            
            # 递归
            self.backtrack(nums, path, used, result)
            
            # 撤销选择（回溯）
            path.pop()
            used[i] = False

方法二：交换法（空间优化）

class SolutionSwap:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        使用交换法生成全排列，空间复杂度更优
        """
        result = []
        self.backtrack_swap(nums, 0, result)
        return result
    
    def backtrack_swap(self, nums: List[int], start: int, 
                      result: List[List[int]]) -> None:
        """
        交换法回溯
        
        Args:
            nums: 数组（会被修改）
            start: 当前处理的位置
            result: 结果集
        """
        # 结束条件
        if start == len(nums):
            result.append(nums[:])
            return
        
        # 尝试将每个元素放到start位置
        for i in range(start, len(nums)):
            # 交换
            nums[start], nums[i] = nums[i], nums[start]
            
            # 递归处理下一个位置
            self.backtrack_swap(nums, start + 1, result)
            
            # 回溯：交换回来
            nums[start], nums[i] = nums[i], nums[start]

方法三：迭代实现

from collections import deque

class SolutionIterative:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        迭代方式生成全排列
        """
        if not nums:
            return []
        
        # 使用队列存储中间结果
        queue = deque([[]])
        
        for num in nums:
            # 处理队列中的每个排列
            for _ in range(len(queue)):
                perm = queue.popleft()
                
                # 将当前数字插入到排列的每个可能位置
                for i in range(len(perm) + 1):
                    new_perm = perm[:i] + [num] + perm[i:]
                    queue.append(new_perm)
        
        return list(queue)

测试代码

def test_permutations():
    """
    测试全排列算法
    """
    solution = Solution()
    
    # 测试用例1
    nums1 = [1, 2, 3]
    result1 = solution.permute(nums1)
    print(f"输入: {nums1}")
    print(f"输出: {result1}")
    print(f"排列数量: {len(result1)}")
    print()
    
    # 测试用例2
    nums2 = [0, 1]
    result2 = solution.permute(nums2)
    print(f"输入: {nums2}")
    print(f"输出: {result2}")
    print(f"排列数量: {len(result2)}")
    print()
    
    # 测试用例3
    nums3 = [1]
    result3 = solution.permute(nums3)
    print(f"输入: {nums3}")
    print(f"输出: {result3}")
    print(f"排列数量: {len(result3)}")

if __name__ == "__main__":
    test_permutations()

📊 复杂度分析

时间复杂度

• O(n × n!)
  • 共有n!个排列
  • 每个排列需要O(n)时间复制到结果集
  • 总时间复杂度：O(n × n!)

空间复杂度

• 标准回溯法：O(n) - 递归栈深度 + used数组
• 交换法：O(n) - 仅递归栈深度
• 结果存储：O(n × n!) - 存储所有排列

性能对比

方法	时间复杂度	空间复杂度	优点	缺点
标准回溯	O(n×n!)	O(n)	思路清晰，易理解	需要额外used数组
交换法	O(n×n!)	O(n)	空间效率高	会修改原数组
迭代法	O(n×n!)	O(n×n!)	无递归调用	空间消耗大

🚀 算法优化

1. 剪枝优化（处理重复元素）

当数组包含重复元素时，需要进行剪枝避免重复排列：

class SolutionII:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        全排列 II：包含重复数字的全排列
        """
        result = []
        path = []
        used = [False] * len(nums)
        
        # 排序是剪枝的前提
        nums.sort()
        
        self.backtrack(nums, path, used, result)
        return result
    
    def backtrack(self, nums: List[int], path: List[int], 
                  used: List[bool], result: List[List[int]]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            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
            
            path.append(nums[i])
            used[i] = True
            
            self.backtrack(nums, path, used, result)
            
            path.pop()
            used[i] = False

2. 内存优化

class SolutionGenerator:
    def permute_generator(self, nums: List[int]):
        """
        生成器版本，按需生成排列，节省内存
        """
        def backtrack(path, used):
            if len(path) == len(nums):
                yield path[:]
                return
            
            for i in range(len(nums)):
                if used[i]:
                    continue
                
                path.append(nums[i])
                used[i] = True
                
                yield from backtrack(path, used)
                
                path.pop()
                used[i] = False
        
        yield from backtrack([], [False] * len(nums))

🔄 变种问题

1. 下一个排列

class NextPermutation:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        找到字典序中下一个更大的排列
        如果不存在，则重新排列成最小的排列
        """
        # 从右向左找到第一个升序对
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        if i >= 0:
            # 从右向左找到第一个大于nums[i]的元素
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            
            # 交换
            nums[i], nums[j] = nums[j], nums[i]
        
        # 反转i+1到末尾的部分
        self.reverse(nums, i + 1)
    
    def reverse(self, nums: List[int], start: int) -> None:
        """反转数组的指定部分"""
        end = len(nums) - 1
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

2. 第k个排列

class KthPermutation:
    def getPermutation(self, n: int, k: int) -> str:
        """
        直接计算第k个排列，不生成所有排列
        """
        # 计算阶乘
        factorial = [1] * n
        for i in range(1, n):
            factorial[i] = factorial[i-1] * i
        
        # 可选数字
        numbers = list(range(1, n + 1))
        result = []
        k -= 1  # 转换为0索引
        
        for i in range(n):
            # 计算当前位置应该选择的数字
            index = k // factorial[n - 1 - i]
            result.append(str(numbers[index]))
            numbers.pop(index)
            k %= factorial[n - 1 - i]
        
        return ''.join(result)

3. 部分排列

class PartialPermutation:
    def permute_partial(self, nums: List[int], k: int) -> List[List[int]]:
        """
        生成长度为k的部分排列
        """
        result = []
        path = []
        used = [False] * len(nums)
        
        self.backtrack(nums, k, path, used, result)
        return result
    
    def backtrack(self, nums: List[int], k: int, path: List[int], 
                  used: List[bool], result: List[List[int]]) -> None:
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            
            path.append(nums[i])
            used[i] = True
            
            self.backtrack(nums, k, path, used, result)
            
            path.pop()
            used[i] = False

🎯 实际应用场景

1. 密码破解

def crack_password(chars: str, length: int):
    """
    生成指定长度的所有可能密码组合
    """
    from itertools import permutations
    
    for perm in permutations(chars, length):
        yield ''.join(perm)

2. 任务调度

def find_optimal_schedule(tasks: List[str]) -> List[str]:
    """
    找到最优的任务执行顺序
    """
    min_cost = float('inf')
    best_schedule = None
    
    for schedule in permutations(tasks):
        cost = calculate_cost(schedule)
        if cost < min_cost:
            min_cost = cost
            best_schedule = schedule
    
    return list(best_schedule)

3. 旅行商问题（TSP）

def tsp_brute_force(cities: List[int], distances: List[List[int]]) -> tuple:
    """
    暴力解法求解旅行商问题
    """
    n = len(cities)
    min_distance = float('inf')
    best_path = None
    
    # 固定起点，对其他城市进行全排列
    for perm in permutations(cities[1:]):
        path = [cities[0]] + list(perm) + [cities[0]]
        distance = sum(distances[path[i]][path[i+1]] for i in range(n))
        
        if distance < min_distance:
            min_distance = distance
            best_path = path
    
    return best_path, min_distance

📝 常见面试题

1. LeetCode 46: 全排列

题目：给定一个不含重复数字的数组nums，返回其所有可能的全排列。

解题要点：

• 理解回溯算法的基本思想
• 正确实现递归和回溯过程
• 注意结果集中需要复制路径

2. LeetCode 47: 全排列 II

题目：给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。

解题要点：

• 排序是剪枝的前提
• 理解剪枝条件：nums[i] == nums[i-1] and not used[i-1]
• 避免重复排列的生成

3. LeetCode 31: 下一个排列

题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

解题要点：

• 理解字典序的概念
• 掌握下一个排列的算法步骤
• 处理边界情况（最大排列）

4. 回溯算法通用模板

def backtrack_template(选择列表, 路径, 结果集):
    """
    回溯算法通用模板
    """
    if 满足结束条件:
        结果集.add(路径)
        return
    
    for 选择 in 选择列表:
        if 选择不合法:
            continue
        
        # 做选择
        路径.add(选择)
        
        # 递归
        backtrack_template(新选择列表, 路径, 结果集)
        
        # 撤销选择
        路径.remove(选择)

📈 性能测试

import time
from itertools import permutations

def performance_test():
    """
    性能测试：比较不同实现方法
    """
    test_cases = [
        [1, 2, 3, 4],
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5, 6]
    ]
    
    solution_backtrack = Solution()
    solution_swap = SolutionSwap()
    
    for nums in test_cases:
        print(f"\n测试数组: {nums} (长度: {len(nums)})")
        
        # 标准回溯法
        start = time.time()
        result1 = solution_backtrack.permute(nums[:])
        time1 = time.time() - start
        
        # 交换法
        start = time.time()
        result2 = solution_swap.permute(nums[:])
        time2 = time.time() - start
        
        # Python内置方法
        start = time.time()
        result3 = list(permutations(nums))
        time3 = time.time() - start
        
        print(f"排列数量: {len(result1)}")
        print(f"标准回溯法: {time1:.6f}s")
        print(f"交换法: {time2:.6f}s")
        print(f"内置方法: {time3:.6f}s")

if __name__ == "__main__":
    performance_test()

🎓 学习总结

核心要点

1. 理解回溯：回溯 = 递归 + 撤销选择
2. 三要素：选择列表、路径、结束条件
3. 模板应用：掌握通用回溯模板
4. 剪枝优化：避免无效搜索，提高效率
5. 空间优化：根据需求选择合适的实现方法

解题技巧

1. 画递归树：可视化理解回溯过程
2. 状态管理：正确维护选择状态
3. 边界处理：注意递归终止条件
4. 结果复制：避免引用问题

常见错误

1. 忘记回溯：没有撤销选择
2. 引用错误：结果集中存储引用而非副本
3. 重复处理：没有正确处理重复元素
4. 边界错误：递归终止条件错误

扩展学习

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

---

总结：全排列是回溯算法的经典入门问题，掌握其原理和实现对理解回溯思想至关重要。通过学习全排列，可以建立起解决其他回溯问题的思维框架，为后续学习更复杂的算法打下坚实基础。