78.子集
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# # 方法1：迭代法
# # 将子集与二进制对应起来
# n = len(nums)
# # 用于存储所有子集
# all_subsets = []
# # 枚举所有 0 到 2^n - 1 的数
# for mask in range(1 << n): # 左移操作，1<<n 表示2^n, 一共有2^n种表示
# current_subset = []
# # 根据 mask 的二进制表示选择元素
# for i in range(n):
# # 检查 mask 的第 i 位是否为 1。如果是，则将 nums[i] 添加到 current_subset 中。
# if mask & (1 << i): # 2^i 作与操作 mask & 1<<i
# current_subset.append(nums[i])
# all_subsets.append(current_subset)
# return all_subsets
# 方法2：递归
# 递归的基本思路：
# 1. 如果我们已经处理了前k个元素，我们需要考虑是否将第k+1个元素加入当前子集
# 2. 对于每个元素，我们都有两种选择：妖魔将它加入当前子集，要么不加入
# 3. 通过递归处理这两种选择，可以生成所有可能的子集
def backtrack(start, path):
# 将当前路径（子集）加入结果集
result.append(path)
# 从当前位置开始，依次尝试每个元素
for i in range(start, len(nums)):
# 递归地生成包含当前元素的子集
backtrack(i + 1, path + [nums[i]])
result = []
backtrack(0, [])
return result
# 方法3：迭代法，这种方法更容易理解一点
# [1 2 3]
# [] [1]
# [] [1] [2] [1 2]
# [] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]
result = [[]]
for num in nums:
temps = []
for subset in result:
temp = subset + [num]
temps.append(temp)
# print(temps)
result.extend(temps)
return result
详细梳理一下递归法生成子集的过程，特别是 backtrack 函数的功能和执行过程。
递归法生成子集的思路
-
递归基础：
- 递归的基本思想是将问题分解为更小的子问题。
- 对于每个元素，我们有两种选择：要么将它加入当前子集，要么不加入。
- 通过递归地处理这两种选择，我们可以生成所有可能的子集。
-
递归函数
backtrack：start参数表示当前递归的起始位置。path参数表示当前构建的子集。
递归函数 backtrack 的功能
-
将当前路径（子集）加入结果集：
- 每次调用
backtrack时，当前的path就是一个新的子集，将其加入结果集result中。
- 每次调用
-
从当前位置开始，依次尝试每个元素：
- 从位置
start开始，依次尝试数组nums中的每个元素。 - 对于每个元素，递归调用
backtrack，生成包含当前元素的子集。
- 从位置
-
递归地生成包含当前元素的子集：
- 对于每个元素
nums[i]，我们递归调用backtrack(i + 1, path + [nums[i]])，这表示在当前路径path的基础上加上nums[i]，并从下一个位置i + 1开始继续生成子集。
- 对于每个元素
代码梳理
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(start, path):
# 将当前路径（子集）加入结果集
result.append(path)
# 从当前位置开始，依次尝试每个元素
for i in range(start, len(nums)):
# 递归地生成包含当前元素的子集
backtrack(i + 1, path + [nums[i]])
result = []
backtrack(0, [])
return result
# 示例用法
solution = Solution()
nums = [5, 2, 9]
print(solution.subsets(nums))
递归过程示例
假设 nums = [5, 2, 9]，我们来看递归过程：
-
初始调用：
backtrack(0, [])result初始为[[]]- 从位置
0开始，尝试元素5
-
递归调用：
backtrack(1, [5])result更新为[[], [5]]- 从位置
1开始，尝试元素2
-
递归调用：
backtrack(2, [5, 2])result更新为[[], [5], [5, 2]]- 从位置
2开始，尝试元素9
-
递归调用：
backtrack(3, [5, 2, 9])result更新为[[], [5], [5, 2], [5, 2, 9]]- 由于
start = 3超出数组长度，返回上一层
-
回溯到位置
2，尝试元素9：backtrack(3, [5, 9])result更新为[[], [5], [5, 2], [5, 2, 9], [5, 9]]
-
回溯到位置
1，尝试元素2：backtrack(2, [2])result更新为[[], [5], [5, 2], [5, 2, 9], [5, 9], [2]]- 从位置
2开始，尝试元素9
-
递归调用：
backtrack(3, [2, 9])result更新为[[], [5], [5, 2], [5, 2, 9], [5, 9], [2], [2, 9]]
-
回溯到位置
0，尝试元素9：backtrack(3, [9])result更新为[[], [5], [5, 2], [5, 2, 9], [5, 9], [2], [2, 9], [9]]
总结
通过递归法，每次调用 backtrack 都会生成一个新的子集，并且通过递归地处理当前元素的选择（加入或不加入），最终生成所有可能的子集。每次递归调用都会在 path 的基础上添加一个新元素，直到遍历完整个数组。
希望这个解释能帮助你更好地理解递归法生成子集的过程。如果还有其他问题，请随时提问！
原文地址：https://blog.csdn.net/weixin_43845922/article/details/142727219
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！