news 2026/4/3 3:11:35

子集- 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/3/15 0:12:57

Excalidraw手势操作指南:触屏设备友好

Excalidraw 手势操作指南:触屏设备友好 在 iPad 上用手指划出一个歪歪扭扭的矩形,再双指一捏放大调整位置,接着喊一声“画个微服务架构”,几秒钟后一组带箭头的服务模块自动排布在画布中央——这不是科幻电影里的场景,…

作者头像 李华
网站建设 2026/3/21 5:02:57

Excalidraw与Tana集成:打造OPML思维导图

Excalidraw与Tana集成:打造OPML思维导图 在知识密度日益提升的今天,团队协作早已不再满足于“写下来”——真正有价值的是如何让灵感快速成型、结构化沉淀,并持续驱动执行。我们经常遇到这样的场景:一场头脑风暴中,白…

作者头像 李华
网站建设 2026/3/14 10:10:55

【专家亲授】Open-AutoGLM迁移学习加速方案:训练时间缩短70%的实操路径

第一章:Open-AutoGLM迁移学习加速的核心价值在深度学习领域,模型训练的效率与资源消耗一直是关键挑战。Open-AutoGLM通过引入高效的迁移学习机制,显著缩短了模型适配新任务的时间周期,同时降低了对大规模标注数据的依赖。其核心价…

作者头像 李华
网站建设 2026/3/30 20:47:30

不再局限于局域网!Open-AutoGLM广域网访问配置的5个关键步骤

第一章:Open-AutoGLM广域网访问概述Open-AutoGLM 是一款基于大语言模型的自动化工具框架,支持在广域网(WAN)环境中实现远程任务调度与智能推理服务部署。其核心优势在于通过轻量级通信协议与加密通道,保障跨网络边界的…

作者头像 李华
网站建设 2026/3/28 12:49:47

Excalidraw如何应对高并发协作场景?

Excalidraw如何应对高并发协作场景? 在远程办公成为常态的今天,团队成员可能分布在不同时区、不同城市,甚至不同的网络环境中。当一场关键的产品评审会议正在进行时,五位工程师正同时在同一个白板上调整架构图:有人拖动…

作者头像 李华