当前位置：首页 > article >正文

Leetcode-100 回溯法-全排列

article 2025/3/20 19:13:55

全排列问题

题目描述

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

示例：

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

解题思路

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

算法步骤

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

代码实现

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = []  # 存放所有排列结果

    def backtrack(start):
        if start == len(nums):  # 终止条件
            res.append(nums[:])  # 复制当前排列结果
            return
        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 res

# 测试
print(permute([1, 2, 3]))

递归的搜索树模型

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

在这里插入图片描述

根节点到叶子节点代表“递归深入”（纵向生长）
- 每进入递归的下一层，相当于深入到搜索树的下一层。
- 例如：在 全排列问题 中，每一层固定一个元素，递归进入下一层。
同一层的不同分支代表“遍历当前层的所有可能”（横向生长）
- 在当前层的 for 循环，遍历所有可能的选择，相当于当前节点的多个分支。
- 例如：在 子集问题 中，每一层都会尝试不同的元素加入子集。

流程示例

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

固定第 0 位：
- 交换 1 和 1 → [1,2,3]
- 递归进入第 1 位：
固定第 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]
交换 1 和 2 → [2,1,3]，继续递归
- 重复上述过程，生成所有排列