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

Leetcode-100 回溯法-子集

article 2025/3/20 18:46:07

子集问题

题目描述

给定一个 互不相同 的整数数组 nums，返回其 所有可能的子集（幂集）。
解集中 不能包含重复的子集，且可以 按任意顺序返回答案。

示例

nums = [1,2,3]
output= [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

解题思路

本题采用 回溯法（Backtracking） 进行求解，核心思想是：

使用递归 搜索所有可能的子集。
子集元素顺序不影响结果，因此 每个元素只能选一次。
每次递归时：
- 将当前 path 加入结果集（构造子集）。
- 递归处理后续元素，搜索新的子集。
- 回溯撤销选择，尝试其他可能的组合。

算法步骤

初始化结果列表
- 创建 存储所有子集 的列表 ans。
- 创建 记录当前路径 的列表 path，用于存储当前递归路径。
定义回溯函数 backtrack(n)
- 添加子集：每次递归先将当前 path（子集）加入 ans，这样所有中间状态都会被记录。
- 终止条件：当 n 超出数组长度时，递归终止。
- 遍历选择：从 n 开始遍历 nums，依次尝试选择元素。
- 选择元素：将 nums[i] 加入 path，表示当前子集包含该元素。
- 递归深入：递归调用 backtrack(i+1) 继续生成子集，避免重复选择相同元素。
- 撤销选择：回溯，移除 path 中的最后一个元素，回到上一层状态，尝试其他可能的分支。
启动递归
- 从起始位置 0 开始调用 backtrack(0)，生成所有子集。

流程示例

以 nums = [1,2,3] 为例，回溯生成所有子集的过程如下：

初始空路径：[] → 加入结果 ans = [[]]。
第一层循环（n=0）：
- 选择 1 → 路径 [1] → 加入结果 ans = [[], [1]]
- 递归进入 n=1：
  - 选择 2 → 路径 [1,2] → 加入结果 ans = [[], [1], [1,2]]
  - 递归进入 n=2：
    - 选择 3 → 路径 [1,2,3] → 加入结果 ans = [[], [1], [1,2], [1,2,3]]
    - 回溯：移除 3，路径变为 [1,2]
  - 回溯：移除 2，路径变为 [1]
  - 选择 3 → 路径 [1,3] → 加入结果 ans = [[], [1], [1,2], [1,2,3], [1,3]]
  - 回溯：移除 3，路径变为 []
第二层循环（n=1）：
- 选择 2 → 路径 [2] → 加入结果 ans = [[], [1], [1,2], [1,2,3], [1,3], [2]]
- 递归进入 n=2：
  - 选择 3 → 路径 [2,3] → 加入结果 ans = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3]]
  - 回溯：移除 3，路径变为 [2]
- 回溯：移除 2，路径变为 []
第三层循环（n=2）：
- 选择 3 → 路径 [3] → 加入结果 ans = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
- 回溯：移除 3，路径变为 []

最终，所有子集被正确生成

代码实现

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
 
        def backtrack(n):
            ans.append(path.copy())  # 记录当前路径状态
            for i in range(n, len(nums)):  # 从位置 n 开始选择元素
                path.append(nums[i])  # 选择当前元素
                backtrack(i + 1)  # 递归：从下一个位置开始
                path.pop()  # 撤销选择，回溯
 
        backtrack(0)
        return ans