代码随想录算法训练营 Day20 | 回溯算法 part02

39. 组合总和给你一个 无重复元素 的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。class Solution { public: vectorint path; vectorvectorint ans; void backtracking(vectorint candidates, int target, int sum, int startIndex) { if (sum target) { ans.push_back(path); return; } // 横向遍历 for (int i startIndex; i candidates.size(); i) { // 剪枝优化因为已经排序如果当前值加 sum 已超标 // 后面的值更大肯定也超标所以可以直接 break (这里写 return 也可以因为这是循环内的最后一层逻辑) // 注意排序是使用 break 的前提 if (sum candidates[i] target) return; path.push_back(candidates[i]); // 关键传入 i表示可以重复选取当前元素 backtracking(candidates, target, sum candidates[i], i); path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); // 预处理排序 backtracking(candidates, target, 0, 0); return ans; } };总结1. 排序的意义排序后数组变为升序例如[2, 3, 6, 7]。逻辑推导如果sum candidates[i]已经大于target因为candidates[i] candidates[i1] ...那么sum candidates[i1]肯定也大于target。结论我们可以直接终止当前层循环而不是仅仅跳过当前元素。2.return与break的细微差别在for循环中标准写法通常建议写break。这表示“结束当前的for循环回到上一层递归”。效果在这个特定的代码结构下return和break的效果是一样的因为return后面的代码本来也不会执行。但为了语义清晰建议养成写break的习惯明确表示“因剪枝而终止循环”。3. 复杂度无排序最坏情况下需要遍历所有分支且剪枝不彻底。有排序剪枝非常“狠”一旦超标立刻切断整条分支。虽然排序本身需要 O(Nlog⁡N)O(NlogN)但在回溯过程中节省的时间往往远超排序的开销。40. 组合总和 II给定一个候选人编号的集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用 一次 。注意解集不能包含重复的组合。class Solution { public: vectorint path; vectorvectorint ans; bool used[101] {false}; // 标记数组记录 candidates[i] 是否在当前路径中被使用 // 回溯函数 // candidates: 候选数组 // target: 目标和 // sum: 当前和 // startIndex: 搜索起点 void backtracking(vectorint candidates, int target, int sum, int startIndex) { if (sum target) { ans.push_back(path); return; } for (int i startIndex; i candidates.size(); i) { // 核心去重逻辑树层去重 // 如果当前元素和前一个相同且前一个元素没被使用过说明是回溯弹出的状态 // 则跳过当前元素避免在同一树层产生重复组合 if (i 0 candidates[i] candidates[i - 1] !used[i - 1]) continue; // 剪枝优化排序后如果当前和超标后续更大元素也超标直接终止 if (sum candidates[i] target) return; used[i] true; // 标记为已使用 path.push_back(candidates[i]); // 关键区别传入 i1因为每个数字在每个组合中只能使用一次 backtracking(candidates, target, sum candidates[i], i 1); path.pop_back(); // 回溯 used[i] false; // 撤销标记 } } vectorvectorint combinationSum2(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); // 排序是去重的前提 backtracking(candidates, target, 0, 0); return ans; } };总结1. 为什么需要used数组因为数组中有重复元素例如[1, 1, 2]简单的startIndex控制只能防止选取之前的索引无法区分是“同一树层”的重复还是“同一树枝”的重复。2. 去重条件代码中的if (i 0 candidates[i] candidates[i - 1] !used[i - 1]) continue;是理解本题的关键candidates[i] candidates[i - 1]说明两个元素值相同。!used[i - 1]说明前一个相同的元素 已经被回溯撤销了即used变回了false。这意味着我们现在处于 同一树层 的遍历中。如果在同一树层遇到相同的值后面的分支必然是前面分支的子集会造成重复结果所以要 跳过 (continue)。这叫 “树层去重”。如果是used[i - 1] true呢说明前一个相同元素正在当前路径中被使用还没撤销我们是顺着前一个元素向下递归的。这属于 “树枝” 上的重复这是允许的例如选取第二个1不需要去重。3. 对比上一题 (39. 组合总和)参数传递上一题传i可重复选取本题传i 1不可重复选取。去重逻辑上一题无重复元素无需去重本题必须通过排序 used数组去重。131. 分割回文串给你一个字符串s请你将s分割成一些 子串使每个子串都是 回文串 。返回s所有可能的分割方案。class Solution { public: vectorstring path; // 当前分割路径 vectorvectorstring ans; // 结果集 // 辅助函数判断字符串是否为回文串 bool isHui(string s) { int l 0, r s.size() - 1; while (l r) { if (s[l] ! s[r--]) return false; // 不相等则不是回文 } return true; } // 回溯函数 // s: 原字符串 // index: 当前分割的起始位置 void backtracking(string s, int index) { // 1. 终止条件起始位置已经超过了字符串长度说明分割完毕 if (index s.size()) { ans.push_back(path); return; } // 2. 单层搜索逻辑 for (int i index; i s.size(); i) { // 获取子串[index, i] 闭区间 string a s.substr(index, i - index 1); // 只有当子串是回文串时才加入路径并继续递归 if (isHui(a)) { path.push_back(a); // 处理节点 backtracking(s, i 1); // 递归从 i1 开始继续分割 path.pop_back(); // 回溯撤销处理结果 } // 如果不是回文串直接跳过相当于剪枝 } } vectorvectorstring partition(string s) { backtracking(s, 0); return ans; } };总结1. 模型转化组合问题从集合中选 k 个数。分割问题将字符串切成 k 段。index代表当前这一刀切在哪里。for循环中的i代表尝试在index到i之间切一段出来。path存储的是切出来的每一段字符串。2. 切割与递归的逻辑横向遍历for循环从index开始尝试切出长度为 1、2、3… 的子串。纵向递归一旦切出一段回文串a就将其加入path然后从i 1开始下一层递归切割剩下的字符串。3. 剪枝优化隐式的剪枝if (isHui(a)) { // 做操作 }如果切出来的子串不是回文就不会进入if块直接进行下一次循环。这避免了进入无效的递归分支条件剪枝。4. 复杂度分析时间复杂度O(N * 2^N)。最坏情况下如全相同字符 “aaaa”每个位置切或不切有 2^N 种方案。判断回文和生成子串需要 O(N) 时间。空间复杂度O(N)。递归深度最大为 N。