Leetcode-100 回溯法-全排列

全排列问题

题目描述

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

示例：

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

解题思路

本解法采用 基于交换的回溯法，通过 原地交换数组元素 生成排列，而不是使用额外的空间存储路径。这种方法的核心思想是 通过递归不断交换数组中的元素，最终生成所有可能的排列。

---

算法步骤

1. 初始化结果列表：创建一个空列表 res 来存储所有排列结果。
2. 定义递归函数 backtrack(start)：
   • 终止条件：当 start == len(nums)，说明排列完成，添加当前 nums 到结果集中。
   • 交换操作：遍历 nums 的每个元素，与 start 位置的元素交换，以固定当前位置的数。
   • 递归深入：调用 backtrack(start + 1) 处理下一个位置的元素。
   • 状态回溯：恢复交换前的数组状态，以进行后续排列的生成。
3. 启动递归：调用 backtrack(0) 开始处理。

代码实现

from typing import Listdef permute(nums: List[int]) -> List[List[int]]:res = []  # 存放所有排列结果def backtrack(start):if start == len(nums):  # 终止条件res.append(nums[:])  # 复制当前排列结果returnfor 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 res# 测试
print(permute([1, 2, 3]))

递归的搜索树模型

在回溯法（Backtracking）和递归算法中，我们可以将 递归过程抽象为一棵搜索树：

• 根节点到叶子节点代表“递归深入”（纵向生长）

  • 每进入递归的下一层，相当于深入到搜索树的下一层。
  • 例如：在 全排列问题 中，每一层固定一个元素，递归进入下一层。

• 同一层的不同分支代表“遍历当前层的所有可能”（横向生长）

  • 在当前层的 for 循环，遍历所有可能的选择，相当于当前节点的多个分支。
  • 例如：在 子集问题 中，每一层都会尝试不同的元素加入子集。

---

流程示例

以 nums = [1,2,3] 为例，演示递归过程：

1. 固定第 0 位：

   • 交换 1 和 1 → [1,2,3]
   • 递归进入第 1 位：

2. 固定第 1 位：

   • 交换 2 和 2 → [1,2,3]
   • 递归进入第 2 位：
     • 交换 3 和 3 → [1,2,3] （排列完成，加入结果）
     • 回溯恢复 [1,2,3]
   • 交换 2 和 3 → [1,3,2] （新排列）
   • 递归进入第 2 位：
     • 交换 2 和 2 → [1,3,2] （排列完成，加入结果）
     • 回溯恢复 [1,2,3]

3. 交换 1 和 2 → [2,1,3]，继续递归

   • 重复上述过程，生成所有排列

---

复杂度分析

• 时间复杂度：O(N!)

  • 共有 N! 种不同的排列，每种排列的生成过程需要 O(N)次操作，因此整体复杂度为 O(N!)。

• 空间复杂度：O(N)

  • 递归调用的最大深度为 N ，即递归栈的最大开销，因此空间复杂度为 O(N) （不计算返回结果占用的额外空间）。