【递归、搜索与回溯算法必刷42题】暴力回溯算法：494. 目标和 + 39. 组合总和-北京尧图网络

个人主页艾莉丝努力练剑❄专栏传送门《C语言》《数据结构与算法》《C/C干货分享学习过程记录》《Linux操作系统编程详解》《笔试/面试常见算法从基础到进阶》《Python干货分享》⭐️为天地立心为生民立命为往圣继绝学为万世开太平艾莉丝的简介文章目录暴力回溯专题494. 目标和 39. 组合总和知识图谱1 ~ 494. 目标和1.1 题目定义1.2 示例 11.3 暴力回溯两种实现1.3.1 方案 1全局变量存储路径和手动回溯恢复现场可能出现的代码上的问题标准代码性能隐患1.3.2 方案 2路径和作为 dfs 形参栈帧自动恢复现场原理说明标准代码1.4 核心结论2 ~ 39. 组合总和2.1 题目定义2.2 示例 12.3 两套暴力回溯解法2.3.1 解法一循环遍历元素原地重复选取核心逻辑标准代码2.3.2 解法二枚举当前数字选取 k 次核心逻辑标准代码2.3.3 小优化结尾暴力回溯专题494. 目标和 39. 组合总和知识图谱1494.目标和LeetCode 中等1.1题目定义1.2示例1.3暴力回溯两种实现方案1.3.1 全局变量记录路径和回溯手动恢复现场1.3.1.1 代码实现1.3.1.2 性能隐患1.3.2 路径和作为dfs参数自动恢复现场1.3.2.1 代码实现1.3.2.2 原理说明1.4核心结论239.组合总和LeetCode 中等2.1题目定义2.2示例2.3两套暴力回溯解法2.3.1 解法一循环枚举每个元素选/不选可重复选取2.3.1.1 代码实现2.3.1.2 核心逻辑说明2.3.2 解法二枚举当前元素选取k次2.3.2.1 代码实现2.3.2.2 现场恢复逻辑2.3.3 小优化点3全域审计错误清单修正方案4最终审计报告1 ~ 494. 目标和1.1 题目定义给定整数数组nums、整数target数组每个数字前添加或-拼接成表达式返回运算结果等于target的不同表达式数量。1.2 示例 1输入nums[1,1,1,1,1], target3输出55 种合法表达式-1111131-1111311-1113111-1131111-131.3 暴力回溯两种实现1.3.1 方案 1全局变量存储路径和手动回溯恢复现场可能出现的代码上的问题类成员变量未初始化多用例测试会出现脏数据无边界溢出注释代码缩进混乱语法排版不标准未说明超时根源全局变量读写频繁现场回滚递归深度大时开销高。标准代码classSolution{private:intpathSum;// 全局路径和intres;// 合法方案总数intaimTarget;// 目标值缓存// pos当前处理数组下标voiddfs(vectorintnums,intpos){// 递归出口遍历完所有数字if(posnums.size()){if(pathSumaimTarget){res;}return;}// 选择 nums[pos]pathSumnums[pos];dfs(nums,pos1);pathSum-nums[pos];// 回溯恢复现场// 选择 -nums[pos]pathSum-nums[pos];dfs(nums,pos1);pathSumnums[pos];// 回溯恢复现场}public:intfindTargetSumWays(vectorintnums,inttarget){// 关键每次调用重置全局变量避免多组用例污染pathSum0;res0;aimTargettarget;dfs(nums,0);returnres;}};性能隐患全局变量读写伴随多次加减恢复操作数组长度较大时极易超时不推荐大数据场景。1.3.2 方案 2路径和作为 dfs 形参栈帧自动恢复现场原理说明每次递归传递path num/path - num每个递归栈帧独立保存当前和上层函数变量不受下层修改影响无需手动撤销操作。标准代码classSolution{private:intres;intaimTarget;// pos当前下标curSum当前分支累计和栈内局部变量voiddfs(vectorintnums,intpos,intcurSum){if(posnums.size()){if(curSumaimTarget){res;}return;}// 选加号新和传入下一层上层curSum不变dfs(nums,pos1,curSumnums[pos]);// 选减号新和传入下一层上层curSum不变dfs(nums,pos1,curSum-nums[pos]);}public:intfindTargetSumWays(vectorintnums,inttarget){res0;aimTargettarget;dfs(nums,0,0);returnres;}};1.4 核心结论整型路径和放函数参数代码简洁、无需手动回溯整型路径和设为全局变量必须手动加减恢复现场易超时暴力搜索仅适合小规模数组本题最优解法为 01 背包动态规划文档未涉及不额外扩展。2 ~ 39. 组合总和2.1 题目定义无重复元素数组candidates、目标值target数字可无限次选取返回所有和等于 target 的不重复组合。判定组合不同选取数字数量不同即不同。2.2 示例 1输入candidates[2,3,6,7], target7输出[[2,2,3],[7]]2.3 两套暴力回溯解法2.3.1 解法一循环遍历元素原地重复选取核心逻辑dfs(candidates, i, sum candidates[i])递归下标仍为i允许重复选取当前数字递归结束后pop_back()撤销当前数字完成回溯。标准代码classSolution{private:intaim;vectorintpath;vectorvectorintresult;// pos起始枚举下标sum当前路径累加和voiddfs(vectorintcandidates,intpos,intsum){// 递归出口1和等于目标保存副本if(sumaim){result.push_back(path);return;}// 递归出口2和超过目标 / 下标越界直接返回if(sumaim||poscandidates.size()){return;}// 从pos开始遍历避免组合重复如[2,3]与[3,2]视为同一组合for(intipos;icandidates.size();i){path.push_back(candidates[i]);// i不变允许重复选取当前数字dfs(candidates,i,sumcandidates[i]);path.pop_back();// 回溯移除当前数字}}public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){aimtarget;path.clear();result.clear();dfs(candidates,0,0);returnresult;}};2.3.2 解法二枚举当前数字选取 k 次核心逻辑循环k代表当前数字选取次数k0代表不选递归进入下一个下标pos1递归全部结束后批量弹出所有存入的数字恢复路径。标准代码classSolution{private:intaim;vectorintpath;vectorvectorintresult;voiddfs(vectorintcandidates,intpos,intsum){if(sumaim){result.push_back(path);return;}if(sumaim||poscandidates.size()){return;}// k当前数字选取次数k0不选intnumcandidates[pos];for(intk0;k*numaim;k){if(k!0){path.push_back(num);}dfs(candidates,pos1,sumk*num);}// 批量回溯弹出本次循环添加的所有numfor(intk1;k*numaim;k){path.pop_back();}}public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){aimtarget;path.clear();result.clear();dfs(candidates,0,0);returnresult;}};2.3.3 小优化循环条件提前叠加已有 sum减少无效循环for(intk1;k*candidates[pos]sumaim;k)结尾uu们本文的内容到这里就全部结束了艾莉丝在这里再次感谢您的阅读艾莉丝努力练剑C/C Linux 底层探索者 | 一个正在努力练剑的技术博主【关注】跟随我一起深耕技术领域见证每一次成长。❤️【点赞】让优质内容被更多人看见让知识传递更有力量。⭐【收藏】把核心知识点存好在需要时随时查、随时用。【评论】分享你的经验或疑问评论区一起交流避坑不要忘记给博主“一键四连”哦“今日练剑达成”“技术之路难免有困惑但同行的人会让前进更有方向。”结语希望对学习Linux相关内容的uu有所帮助不要忘记给博主“一键四连”哦往期回顾【递归、搜索与回溯算法必刷42题专题一】从汉诺塔问题到快速幂博主在这里放了一只小狗大家看完了摸摸小狗放松一下吧૮₍ ˶ ˊ ᴥ ˋ˶₎ა

【递归、搜索与回溯算法必刷42题】暴力回溯算法：494. 目标和 + 39. 组合总和

相关推荐

Paperxie 毕业论文 AI 写作：分阶式创作体系，一站式化解毕业撰文各类难题

如何让AI看懂企业“业务语言”？从企业数据孤岛到统一认知引擎

爆火的Codex人人跟风试用？绝大多数科研人其实根本用不明白

更多资讯

电工证被人使用如何查郑州报考避坑指南

电工证鄂托克旗实操考试考什么？官方报名入口你一定要知道

电工证的头像怎么更换？官方报名入口你必须知道

高压电工证有什么补贴怎么报名最稳妥

电工证广告视频真实经历：工地太忙根本没时间复习考试怎么办

宜阳县电工证丢了怎么补办保姆级教程：缺证就缺饭碗，这份教程帮你稳稳上岗

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

Paperxie 毕业论文 AI 写作：分阶式创作体系，一站式化解毕业撰文各类难题

如何让AI看懂企业“业务语言”？从企业数据孤岛到统一认知引擎

爆火的Codex人人跟风试用？绝大多数科研人其实根本用不明白

更多资讯

电工证被人使用如何查 郑州报考避坑指南

电工证鄂托克旗实操考试考什么？官方报名入口你一定要知道

电工证的头像怎么更换？官方报名入口你必须知道

高压电工证有什么补贴 怎么报名最稳妥

电工证广告视频真实经历：工地太忙根本没时间复习考试怎么办

宜阳县电工证丢了怎么补办保姆级教程：缺证就缺饭碗，这份教程帮你稳稳上岗

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

电工证被人使用如何查郑州报考避坑指南

高压电工证有什么补贴怎么报名最稳妥

新疆电工作业干活累吗良心建议助你避开考不过的坑

新疆电工作业干活累吗良心建议助你避开考不过的坑