回溯

491. 递增子序列 链接：491. 递增子序列 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 这题不能排序，同层去重又不会了； 看完题解后的想法 使用 set 记录本层使用过的数据，这是更加一般的同层去重； 实现中遇到的困难 不会非排序的同层去重； 代码 class Solution { public: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int index) { if (path.size() >= 2) { res.push_back(path); } unordered_set<int> used; // 每层一个，记录本层用过的值 for (int i = index; i < nums.size(); i++) { if ((!path.empty() && nums[i] < path.back()) || used.count(nums[i])) { continue; } used.insert(nums[i]); // 注意退栈不用 erase，因为还在当前层 path.push_back(nums[i]); backtracking(nums, i+1); path.pop_back(); } } vector<vector<int>> findSubsequences(vector<int>& nums) { backtracking(nums, 0); return res; } }; 46. 全排列 链接：46. 全排列 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 排列不需要传入 index，因为每次都是从头访问； ...

93. 复原IP地址 链接：93. 复原IP地址 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 和分割回文串类似，不是去构造一个合法的子串，而是去直接分割，不合法就 skip； 看完题解后的想法 – 实现中遇到的困难 最开始 path 是一个 str，对于 IP 地址要求的四段判断比较复杂； path 在这里也需要是 vector，这样回溯才方便；最后直接构造一个返回字符串就行； 代码 class Solution { public: bool isValid(string& s) { if (s.size() > 1 && s[0] == '0') return false; if (stoi(s) > 255) return false; return true; } vector<string> res; vector<string> path; void backtracking(string s, int index) { if (path.size() == 4) { if (index == s.size()) { res.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]); } return; // 不管是否收集，4段了就不再递归 } for (int i = index; i < s.size() && i - index < 3; i++) { string str = s.substr(index, i - index + 1); if (isValid(str)) { path.push_back(str); backtracking(s, i+1); path.pop_back(); } else { break; // 当前不合法后面更长也不合法 } } } vector<string> restoreIpAddresses(string s) { if (s.size() > 12 || s.size() < 4) { return res; } backtracking(s, 0); return res; } }; 78. 子集 链接：78. 子集 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 自己做的时候考虑到符合条件的子集大小是变动的，就在回溯外面套了一个 while 循环去增加 size； ...

39. 组合总和 链接：39. 组合总和 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 回溯三部曲； 看完题解后的想法 可以用排序加速剪枝； 实现中遇到的困难 – 代码 class Solution { public: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& candidates, int target, int index, int sum) { if (sum == target) { res.push_back(path); return; } for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) { sum += candidates[i]; path.push_back(candidates[i]); backtracking(candidates, target, i, sum); sum -= candidates[i]; path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return res; } }; 40. 组合总和II 链接：40. 组合总和II 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 依旧回溯三部曲，但是注意同层去重逻辑； ...

回溯算法理论基础 文章：代码随想录 - 回溯算法理论基础 视频：B站讲解 77. 组合 链接：77. 组合 文章：代码随想录 视频：B站讲解 剪枝：B站讲解 状态：❌ 第一想法 第一想法是回溯，但是对于如何存 path，如何回溯有点摸不着头脑; 看完题解后的想法 不用复杂的递归返回，只把递归作为前进的路径，直接使用外部空间保存路径; 外部空间必须在退出递归时 pop 数据，这就是回溯; 实现中遇到的困难 剪枝条件写起来很复杂，但是搞清楚了如何剪枝就能马上写出来; 代码 class Solution { public: /* 回溯的模板可以这样理解： 1. 路径 (path)：当前已经选了哪些数 2. 选择列表：从 start 到 n，还能选哪些数 3. 结束条件：path.size() == k 时，收集结果 */ vector<vector<int>> res; vector<int> path; void backtracking(int n, int k, int start) { // 返回条件：找到k个数 if (path.size() == k) { res.push_back(path); return; } /* 剪枝优化： 当前已有数字 path.size() 个, 还需数字 k - path.size() 个 在 i 到 n 之间有 n - i + 1个数字 n - i + 1 >= k - path.size() */ for (int i = start; i <= n + 1 + path.size() - k; i++) { path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracking(n, k, 1); return res; } }; 216. 组合总和III 链接：216. 组合总和III 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 回溯三部曲： ...