当前位置：首页 > backend >正文

力扣DAY56-59 | 热100 | 回溯：子集、电话号码的字母组合、组合总和、括号生成

backend 2025/5/21 1:37:49

前言

中等 √ 怒刷回溯，逐渐有了手感，重点就在于设计树+复原状态+sometimes剪枝。

子集

我的题解

全排列的基础上修改：1）每个状态（而不是size等于数组长度）都加入答案数组中。2）设置指针，下一个状态从当前指针位置开始遍历point = i。

class Solution {
public:vector<int> visited;void findans(vector<vector<int>>& ans, vector<int>& nums, vector<int> subans, int point){for (int i = 0; i < nums.size(); i++){if (visited[i] == 0){visited[i] = 1;subans.push_back(nums[i]);if (i >= point){ans.push_back(subans);findans(ans, nums, subans, i);}subans.pop_back(); // 重点！状态复原！！visited[i] = 0;}}}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;visited.resize(nums.size());ans.push_back({});findans(ans, nums, {}, 0);return ans;}
};

官方题解

我们也可以用递归来实现子集枚举。

假设我们需要找到一个长度为 n 的序列 a 的所有子序列。

原序列的每个位置在答案序列中的状态有被选中和不被选中两种，我们用 t 数组存放已经被选出的数字。在进入 dfs(cur,n) 之前 [0,cur−1] 位置的状态是确定的，而 [cur,n−1] 内位置的状态是不确定的，dfs(cur,n) 需要确定 cur 位置的状态，然后求解子问题 dfs(cur+1,n)。对于 cur 位置，我们需要考虑 a[cur] 取或者不取，如果取，我们需要把 a[cur] 放入一个临时的答案数组中（即上面代码中的 t），再执行 dfs(cur+1,n)，执行结束后需要对 t 进行回溯；如果不取，则直接执行 dfs(cur+1,n)。在整个递归调用的过程中，cur 是从小到大递增的，当 cur 增加到 n 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2 n )。

class Solution {
public:vector<int> t;vector<vector<int>> ans;void dfs(int cur, vector<int>& nums) {if (cur == nums.size()) {ans.push_back(t);return;}t.push_back(nums[cur]);dfs(cur + 1, nums);t.pop_back();dfs(cur + 1, nums);}vector<vector<int>> subsets(vector<int>& nums) {dfs(0, nums);return ans;}
};

心得

这道题跟全排列非常类似，区别之处在于如何剪枝（终止条件）和最终状态规则（什么情况加入答案数组）。而官解给出另一种解法：每个节点选与不选。固定前序节点，遍历下一个节点，选push，不选pop。

电话号码的字母组合

我的题解

每一层是对应电话号码的一位，遍历该层每个字母，加字母后遍历下一层，然后回溯到本层遍历下一个字母。

class Solution {
public:vector<vector<char>> number;vector<string> ans;void findans(string digits, int point, string substr){if (point == digits.length()){ans.push_back(substr);return;}int n = digits[point]-'2';for(int i = 0; i < number[n].size(); i++){substr += number[n][i];findans(digits, point + 1, substr);substr.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.empty()) return {};number.resize(9);number = {{'a', 'b', 'c'},{'d', 'e', 'f'},{'g', 'h', 'i'},{'j', 'k', 'l'},{'m', 'n', 'o'},{'p', 'q', 'r', 's'},{'t', 'u', 'v'},{'w', 'x', 'y', 'z'}};findans(digits, 0, {});return ans;}
};

官方题解

与笔者一致，不赘叙。

心得

这题比较顺手，逐渐会比较熟悉地把设计出来的树转成代码了。

组合总和

我的题解

定义变量prenum记录前序数组，presum记录前序数组合，指针point用于只遍历后置位数组（每次point = i）。剪枝条件：数组越界，和大于目标值。加入答案数组条件：和等于目标值。

class Solution {
public:vector<vector<int>> ans;void findans(vector<int>& candidates, int target, vector<int> prenum, int presum, int point){if (point >= candidates.size()) return;if (presum > target) return;for (int i = point; i < candidates.size(); i++){presum += candidates[i];prenum.push_back(candidates[i]);if (presum == target) ans.push_back(prenum);findans(candidates, target, prenum, presum, i);presum -= candidates[i];prenum.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if(target < 2) return {};findans(candidates, target, {}, 0, 0);return ans;}
};

官方题解

无剪枝版本

心得

逐渐明白回溯的重点在于如何定义每个节点的状态，跟上一状态有啥区别。而剪枝是优化效率的关键。

括号生成

我的题解

定义二维数组存储左右括号剩余的数量，当剩余左右括号小于等于0时加入答案数组并剪枝。当右括号少于左括号时剪枝。遍历左右括号，当左括号为空时只能进右括号，跳过。递归前前置序列加括号，对应括号数量减一，递归后复原。

class Solution {
public:vector<string> ans;vector<int> LR;vector<char> LRc;void findans(string prestr){if(LR[1] <= 0 && LR[0] <= 0){ans.push_back(prestr);return;}if(LR[1] < LR[0]) return;for (int i = 0; i < 2; i++){if (i == 0 && LR[i] <= 0) i++;prestr += LRc[i];LR[i]--;findans(prestr);LR[i]++;prestr.pop_back();}}//L为空，R进；R为空，returnvector<string> generateParenthesis(int n) {LR = {n, n};LRc = {'(', ')'};findans({});return ans;}
};