news 2026/4/15 21:03:23

子集- 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/13 17:47:09

Excalidraw绘图规范建议:打造统一视觉语言

Excalidraw绘图规范建议:打造统一视觉语言 在一次远程技术评审会上,你是否经历过这样的场景?有人滔滔不绝地描述一个复杂的微服务调用链,而其他成员却面露困惑,直到某人突然说:“等等,让我画一下…

作者头像 李华
网站建设 2026/4/13 6:23:55

从配置到上线:Open-AutoGLM局域网部署全流程详解,AI落地不再难

第一章:Open-AutoGLM局域网部署方案概述Open-AutoGLM 是一款基于开源大语言模型的自动化推理服务框架,支持在局域网环境中进行本地化部署,保障数据隐私与服务可控性。该方案适用于企业内网、科研机构等对数据安全要求较高的场景,能…

作者头像 李华
网站建设 2026/4/14 17:04:13

【高危漏洞预警】未正确配置Open-AutoGLM认证将导致数据泄露?

第一章:Open-AutoGLM 安全访问认证Open-AutoGLM 作为开源自动化大语言模型网关,其安全访问机制是系统可信运行的核心。为确保接口调用的合法性与数据传输的机密性,系统采用多层级认证策略,涵盖 API 密钥验证、JWT 令牌签发及双向 …

作者头像 李华
网站建设 2026/4/16 9:16:58

千万不能忽视!选择实验室操作台的5大关键点

千万不能忽视!选择实验室操作台的5大关键点引言在现代科研和工业生产中,实验室操作台实验台是不可或缺的基础设备。一个优质的实验室操作台不仅能提升工作效率,还能确保实验的安全性和准确性。那么,在选择实验室操作台时&#xff…

作者头像 李华
网站建设 2026/4/15 20:51:26

如何在5分钟内完成Open-AutoGLM安全认证加固?(附配置模板)

第一章:Open-AutoGLM 安全访问认证Open-AutoGLM 作为开源自动化大语言模型网关,其安全访问机制是系统稳定运行的核心保障。为确保只有授权用户和应用能够调用模型服务,系统采用多层级认证策略,结合 API 密钥、JWT 令牌与客户端证书…

作者头像 李华
网站建设 2026/4/16 2:20:07

Windows系统文件DataExchange.dll缺失或损坏问题 下载修复

在使用电脑系统时经常会出现丢失找不到某些文件的情况,由于很多常用软件都是采用 Microsoft Visual Studio 编写的,所以这类软件的运行需要依赖微软Visual C运行库,比如像 QQ、迅雷、Adobe 软件等等,如果没有安装VC运行库或者安装…

作者头像 李华