news 2026/4/6 14:03:05

子集- python-回溯

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
子集- python-回溯

题目:

思路:

  • 启动阶段:初始化空结果集 res,调用回溯函数 backtrack([], 0),以空路径为起点,从数组第0个元素开始遍历选择

  • 递归遍历阶段:进入回溯函数后,先将当前路径副本存入 res,再从 start 索引开始遍历数组元素,依次执行“选元素→递归调用→撤销选择”的循环

  • 回溯探索阶段:每次递归调用将 start 索引+1,限制后续选择范围,递归返回后通过 pop() 撤销选择,切换到“不选当前元素”的分支继续遍历

  • 终止与收尾阶段:当遍历索引超出数组长度时,递归自然终止,所有分支遍历完成后,res 已收集全部子集,最终返回 res

代码:

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(path,start): res.append(path.copy()) for i in range(start,len(nums)): path.append(nums[i]) backtrack(path,i+1) path.pop() backtrack([],0) return res

例子:

nums = [1,2,3]为例,一步步拆解回溯法的执行过程

回溯函数的两个关键参数:

  • path:当前已选中的元素
  • start:当前开始遍历的索引(避免重复选,比如选了 2 就不再回头选 1)。

核心规则:每次进入回溯函数,先把当前path加入结果集(哪怕是空集),再遍历start到末尾的元素,依次做 “选” 或 “不选” 的决策。


步骤 1:初始调用backtrack([], 0)

此时path = []start = 0

  • 第一步:把[]加入结果集(结果集现在:[[]]);
  • 第二步:遍历i = 0,1,2(对应元素 1、2、3),先处理i=0(元素 1)。
决策 1:选元素 1
  • path变为[1],递归调用backtrack([1], 1)start变为 1,因为下一个只能选 2、3)。

步骤 2:执行backtrack([1], 1)

此时path = [1]start = 1

  • 第一步:把[1]加入结果集(结果集:[ [], [1] ]);
  • 第二步:遍历i = 1,2(对应元素 2、3),先处理i=1(元素 2)。
决策 2:选元素 2
  • path变为[1,2],递归调用backtrack([1,2], 2)start变为 2,下一个只能选 3)。

步骤 3:执行backtrack([1,2], 2)

此时path = [1,2]start = 2

  • 第一步:把[1,2]加入结果集(结果集:[ [], [1], [1,2] ]);
  • 第二步:遍历i = 2(对应元素 3),处理i=2(元素 3)。
决策 3:选元素 3
  • path变为[1,2,3],递归调用backtrack([1,2,3], 3)start变为 3,超出数组长度)。

步骤 4:执行backtrack([1,2,3], 3)

此时start = 3,超出数组长度(len(nums)=3),遍历循环不执行。

  • 第一步:把[1,2,3]加入结果集(结果集:[ [], [1], [1,2], [1,2,3] ]);
  • 第二步:无遍历,递归返回。
回溯:撤销 “选 3” 的决策

回到backtrack([1,2], 2),执行path.pop()path变回[1,2]

  • 遍历i=2处理完毕,无更多i,递归返回。
回溯:撤销 “选 2” 的决策

回到backtrack([1], 1),执行path.pop()path变回[1]

  • 继续处理遍历的下一个i=2(元素 3)。

步骤 5:回到backtrack([1], 1),处理i=2(元素 3)

决策 4:选元素 3
  • path变为[1,3],递归调用backtrack([1,3], 3)start=3)。
执行backtrack([1,3], 3)
  • 第一步:把[1,3]加入结果集(结果集:[ [], [1], [1,2], [1,2,3], [1,3] ]);
  • 第二步:无遍历,递归返回。
回溯:撤销 “选 3” 的决策

回到backtrack([1], 1),执行path.pop()path变回[1]

  • 遍历i=1,2处理完毕,递归返回。
回溯:撤销 “选 1” 的决策

回到初始的backtrack([], 0),执行path.pop()path变回[]

  • 继续处理遍历的下一个i=1(元素 2)。

步骤 6:初始调用处理i=1(元素 2)

决策 5:选元素 2
  • path变为[2],递归调用backtrack([2], 2)start=2)。
执行backtrack([2], 2)
  • 第一步:把[2]加入结果集(结果集:[ [], [1], [1,2], [1,2,3], [1,3], [2] ]);
  • 第二步:遍历i=2(元素 3),处理i=2
决策 6:选元素 3
  • path变为[2,3],递归调用backtrack([2,3], 3)
执行backtrack([2,3], 3)
  • 第一步:把[2,3]加入结果集(结果集:[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3] ]);
  • 第二步:无遍历,递归返回。
回溯:撤销 “选 3”→ 撤销 “选 2”

回到初始的backtrack([], 0)path变回[],继续处理i=2(元素 3)。


步骤 7:初始调用处理i=2(元素 3)

决策 7:选元素 3
  • path变为[3],递归调用backtrack([3], 3)
执行backtrack([3], 3)
  • 第一步:把[3]加入结果集(最终结果集:[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]);
  • 第二步:无遍历,递归返回。
回溯:撤销 “选 3”

回到初始的backtrack([], 0),遍历结束,整个回溯过程完成。


版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/4/3 6:05:44

【紧急预警】Open-AutoGLM旧版本将停服?迁移兼容方案限时公开

第一章:Open-AutoGLM 系统版本兼容优化在部署 Open-AutoGLM 框架时,系统版本的兼容性直接影响模型训练与推理的稳定性。不同操作系统及依赖库版本可能导致接口不一致、编译失败或运行时异常。为确保跨平台一致性,需对核心依赖项进行版本锁定&…

作者头像 李华
网站建设 2026/3/22 13:51:20

Excalidraw深度解析:为什么它成为开发者最爱的绘图工具?

Excalidraw深度解析:为什么它成为开发者最爱的绘图工具? 在一次深夜的技术评审会上,团队正为“用户登录流程如何与微服务网关交互”争论不休。有人贴出一段文字描述,另一人画了个草图拍照上传——结果因为箭头指向模糊&#xff0…

作者头像 李华
网站建设 2026/4/5 13:15:43

为什么你的迁移学习总失败?Open-AutoGLM这3个坑千万别踩

第一章:为什么你的迁移学习总失败?Open-AutoGLM这3个坑千万别踩在使用 Open-AutoGLM 进行迁移学习时,许多开发者虽具备基础模型调用能力,却频繁遭遇性能不升反降、收敛困难甚至训练崩溃的问题。究其原因,往往源于对框架…

作者头像 李华
网站建设 2026/3/31 14:19:53

版本升级总失败?Open-AutoGLM兼容性痛点全解析,一文搞定

第一章:版本升级总失败?Open-AutoGLM兼容性痛点全解析在实际部署与维护 Open-AutoGLM 的过程中,开发者频繁遭遇版本升级失败的问题。这些故障往往并非源于代码逻辑缺陷,而是由模块间隐性的兼容性冲突所致。尤其在引入新功能或依赖…

作者头像 李华
网站建设 2026/3/23 1:06:38

技术文档配图新选择:Excalidraw手绘风更吸睛

技术文档配图新选择:Excalidraw手绘风更吸睛 在一次远程架构评审会上,团队正讨论一个微服务系统的调用链路。主讲人共享屏幕,打开的不是常见的 Visio 或 Draw.io 图表,而是一张看起来像是“手绘”的架构草图——线条略带抖动&…

作者头像 李华
网站建设 2026/3/27 18:07:46

为什么90%的Open-AutoGLM集成项目忽视了这1个认证风险?

第一章:Open-AutoGLM 安全访问认证Open-AutoGLM 提供基于令牌的细粒度访问控制机制,确保模型调用过程中的安全性与可审计性。所有客户端请求必须携带有效的 JWT(JSON Web Token)令牌,并通过网关层的身份验证中间件校验…

作者头像 李华