news 2026/4/23 13:43:46

子集- 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/23 13:43:31

零基础学大数据隐私保护:3个月学习计划+推荐书籍_课程_工具

零基础学大数据隐私保护:3个月系统学习计划权威资源推荐 元数据框架 标题:零基础入门大数据隐私保护:3个月阶梯式学习计划(附书籍/课程/工具清单) 关键词:大数据隐私保护;零基础学习计划&#x…

作者头像 李华
网站建设 2026/4/23 12:12:10

Excalidraw与Figma的互补使用场景

Excalidraw 与 Figma:从草图到交付的设计协同之道 在一场典型的产品需求评审会上,产品经理刚讲完新功能设想,会议室陷入沉默——没人真正“看见”他口中的流程。直到有人打开 Excalidraw,在白板上随手画出三个框和几条箭头&#x…

作者头像 李华
网站建设 2026/4/20 0:20:58

告别平台锁定:Open-AutoGLM实现Windows/Linux/macOS一致性运行的4个关键技术

第一章:Open-AutoGLM 跨平台部署适配在构建高效的AI推理服务时,Open-AutoGLM 的跨平台部署能力成为关键环节。为确保模型在不同操作系统与硬件架构下稳定运行,需针对目标环境进行系统级适配与优化。环境依赖配置 部署前需统一管理运行时依赖&…

作者头像 李华
网站建设 2026/4/5 23:27:11

(首次公开)Open-AutoGLM多端部署适配框架设计全貌

第一章:Open-AutoGLM 跨平台部署适配在构建现代化AI推理系统时,Open-AutoGLM 的跨平台部署能力成为关键。为确保模型在不同操作系统(如Linux、Windows、macOS)和硬件架构(x86、ARM)上稳定运行,需…

作者头像 李华
网站建设 2026/4/17 17:24:11

Excalidraw开源白板工具:用AI快速生成手绘风格技术架构图

Excalidraw:当手绘白板遇上AI,技术架构图从此“说画就画” 在一次深夜的远程架构评审会上,团队卡在了最基础的问题上——没人能快速讲清楚当前系统的调用链路。有人翻出三个月前的Visio图发现早已过时,另一位同事尝试在聊天窗口贴…

作者头像 李华
网站建设 2026/4/23 11:51:30

Open-AutoGLM适配难?掌握这5个核心参数,轻松实现零样本迁移

第一章:Open-AutoGLM预训练模型适配概述Open-AutoGLM 是面向自动化任务理解与生成的通用大语言模型,其核心优势在于对多领域指令的理解能力与上下文推理性能。在实际应用中,为充分发挥该模型潜力,需针对特定业务场景进行预训练模型…

作者头像 李华