news 2026/5/26 8:10:09

子集- 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/5/25 17:40:25

基于Excalidraw的定制化企业白板解决方案

基于 Excalidraw 的定制化企业白板解决方案 在远程办公常态化、跨地域协作日益频繁的今天,团队对“看得见”的沟通方式提出了更高要求。无论是产品原型讨论、系统架构设计,还是敏捷迭代中的任务拆解,一张能实时共创的虚拟白板,早…

作者头像 李华
网站建设 2026/5/25 12:17:35

Excalidraw图层管理功能进阶用法

Excalidraw图层管理功能进阶用法 在远程协作日益成为常态的今天,技术团队对可视化工具的需求早已超越“画个框连条线”的初级阶段。一张清晰、可维护、易于沟通的架构图,往往决定了需求评审能否高效推进,或是故障复盘是否能快速达成共识。Exc…

作者头像 李华
网站建设 2026/5/26 5:16:40

Excalidraw绘图快捷键大全(建议收藏)

Excalidraw绘图快捷键大全(建议收藏) 在远程协作和敏捷开发成为常态的今天,团队对可视化工具的要求早已不再局限于“能画图”。我们需要的是一个既能激发创意、又不拖慢节奏的数字白板——而 Excalidraw 正是这样一款让人一用就回不去的工具。…

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

Excalidraw性能调优:大规模图形渲染优化

Excalidraw性能调优:大规模图形渲染优化 在现代远程协作日益深入的背景下,可视化工具早已不再是“锦上添花”的辅助软件,而是产品设计、系统架构和团队沟通的核心载体。Excalidraw 凭借其独特的手绘风格、轻量级交互和出色的可扩展性&#xf…

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

Excalidraw支持手写笔输入,还原真实绘图手感

Excalidraw:用一支虚拟手写笔,唤醒数字创作的原始本能 在 iPad 上用 Apple Pencil 轻轻一划,一条微微抖动的线条跃然“纸”上——不完美,却格外真实。这不是某位艺术家的手绘本,而是 Excalidraw 正在实时渲染的一张系统…

作者头像 李华
网站建设 2026/5/25 15:32:39

为什么越来越多企业选择局域网部署Open-AutoGLM?3个你必须知道的安全优势

第一章:Open-AutoGLM局域网部署的背景与趋势随着企业对数据隐私和模型可控性的要求日益提升,大语言模型在私有化环境中的部署逐渐成为主流选择。Open-AutoGLM 作为一款支持自动化任务处理的开源语言模型,其在局域网内的本地化部署不仅能够保障…

作者头像 李华