代码随想录二刷|回溯2

回溯

组合问题

方法

组合

题干

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路

（1）定义全局变量数组，作为存放组合的数组和存放最终答案的数组

（2）如果组合长度为k，加入答案，返回

（3）从起始的index出发，直到n，一次放入组合，递归调用下一个下标作为index，再弹出组合里面的index

1）起始的index表示考虑放入组合的元素开始的下标，index=2就是从下标为2的元素开始考虑是否加入组合

2）为什么递归调用的时候用i+1作为起始的index：已经选择了下标为i的元素，不走回头路，也不能重复选取

class Solution {
public:vector<vector<int>>res;vector<int>ans;void f(int n,int k,int index){if(ans.size()==k){res.push_back(ans);return;}// if(index+k>n){//     return;// }for(int i=index;i<=n;i++){ans.push_back(i);f(n,k,i+1);ans.pop_back();}}vector<vector<int>> combine(int n, int k) {f(n,k,1);return res;}
};

组合的优化

题干

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路

优化点：遍历的终点从n改成n-(k-ans.size())+1

因为如果剩下的元素不足够填满组合，就停下来

（n = 4，k = 3，目前已经选取的元素数为0（ans.size为0），现在的index是1，n - (k - index) + 1 即 4 - ( 3 - 1) + 1 = 3，也就是说，组合的第一个匀速可以是1或2或3）

class Solution {
public:vector<vector<int>>res;vector<int>ans;void f(int n,int k,int index){if(ans.size()==k){res.push_back(ans);return;}for(int i=index;i<=n-(k-ans.size())+1;i++){ans.push_back(i);f(n,k,i+1);ans.pop_back();}}vector<vector<int>> combine(int n, int k) {f(n,k,1);return res;}
};

组合之和III

题干

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路

（1）结束条件：组合长度到k的时候，如果组合之和是n，那么存答案。无论组合之和是否为n，只要长度到k，都要返回

（2）遍历：从起始值到9，依次加入组合，递归调用下一个值，将现在的元素从组合拿走

class Solution {
public:vector<vector  <int>>res;vector<int> ans;void f(int k,int n,int index){if(ans.size()==k){int s=0;for(int j=0;j<k;j++){s+=ans[j];}if(s==n)res.push_back(ans);return;}for(int i=index;i<=9;i++){ans.push_back(i);f(k,n,i+1);ans.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {f(k,n,1);return res;}
};

电话号码的字母

题干

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路

（1）首先找到数字和字母的映射

（2）递归参数：digits（数字构成的字符串），和character_index（表示现在要寻找并加入第几个数字对应的字母）

（3）递归终点：如果character_index等于数字个数，就返回

（4）先把当前考虑的数字从字符变成数字，再获取这个数字对应的字符串

（5）遍历这个字符串的所有字符，加入组合，递归输入当中的下一个数字，将字符移出组合

（6）额外加上对空输入的处理

class Solution {
public:string ans;vector<string> res;vector<string> match = {"",    "",    "abc",  "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};void f(string digits, int character_index) {if (character_index == digits.size()) {res.push_back(ans);return;}int index = digits[character_index] - '0';string letter = match[index];for (int i = 0; i < letter.size(); i++) {ans.push_back(letter[i]);f(digits, character_index + 1);ans.pop_back();}}vector<string> letterCombinations(string digits) {if (digits.size() == 0)return res;f(digits, 0);return res;}
};

组合总和

题干

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

（1）递归终点：

sum大于target返回

sum等于target存答案并返回

（2）从起始下标开始，迭代

1）加入组合，求sum

2）递归调用，注意起始下标改成i

表示在下标为i的元素加入组合之后，不走回头路，可以重复用下标为i的元素

3）弹出，sum减掉

class Solution {
public:vector<int> ans;vector<vector<int>> res;void f(vector<int>& candidates, int target, int sum, int start_i) {if (sum > target)return;if (sum == target) {res.push_back(ans);return;}for (int i = start_i; i < candidates.size(); i++) {ans.push_back(candidates[i]);sum += candidates[i];f(candidates, target, sum, i);sum -= candidates[i];ans.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {f(candidates, target, 0, 0);return res;}
};

组合之和II

题干

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

思路

基本思路

（1）回溯框架

终止条件：和为target存答案，和大于target返回

单次递归：for循环，每次从start开始，加入组合+更新sum+更新used，递归调用（start为i+1），回溯（恢复组合，sum，used）

（2）去重：

1）重复的地方：candidates有重复的两个元素，考虑完第一个之后，再考虑第二个的话会产生一样的组合

2）解决：used标记元素是否在组合中使用

如果candidates[i] 和candidates[i - 1]相等，并且candidates[i - 1]没有在组合中使用（说明已经考虑过了candidates[i - 1]的所有组合），跳过

注意：先对candidates排队序，确保相同元素挨着

class Solution {
public:vector<int> ans;vector<vector<int>> res;void f(vector<int>& candidates, int target, int start, vector<int> used,int sum) {if (sum == target) {res.push_back(ans);return;}if (sum > target)return;for (int i = start; i < candidates.size(); i++) {if (i > 0 && candidates[i] == candidates[i - 1] &&used[i - 1] == false)continue;ans.push_back(candidates[i]);sum += candidates[i];used[i] = true;f(candidates, target, i + 1, used, sum);used[i] = false;sum -= candidates[i];ans.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<int> used(candidates.size(), false);sort(candidates.begin(), candidates.end());f(candidates, target, 0, used, 0);return res;}
};

剪枝优化

在for循环里，如果现有的和加上当前元素大于target，就停止循环（作为循环停止条件）

class Solution {
public:vector<int> ans;vector<vector<int>> res;void f(vector<int>& candidates, int target, int start, vector<int> used,int sum) {if (sum == target) {res.push_back(ans);return;}for (int i = start;i < candidates.size() && sum + candidates[i] <= target; i++) {if (i > 0 && candidates[i] == candidates[i - 1] &&used[i - 1] == false)continue;ans.push_back(candidates[i]);sum += candidates[i];used[i] = true;f(candidates, target, i + 1, used, sum);used[i] = false;sum -= candidates[i];ans.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<int> used(candidates.size(), false);sort(candidates.begin(), candidates.end());f(candidates, target, 0, used, 0);return res;}
};

回文子串

思路

for循环遍历的起点是start，每次寻找子字符串[start,i] ，如果是回文就加入组合，递归，不是就continue

class Solution {
public:vector<vector<string>> res;vector<string> ans;bool is_hui(string s, int l, int r) {for (int i = l; i <= r; i++) {if (s[i] != s[r - (i - l)])return false;}return true;}void f(string s, int start) {if (start >= s.size()) {res.push_back(ans);}for (int i = start; i < s.size(); i++) {if (is_hui(s, start, i)) {// string str(s.begin() + start, s.begin() + start + i + 1);string str = s.substr(start, i - start + 1);ans.push_back(str);f(s, i + 1);ans.pop_back();}}}vector<vector<string>> partition(string s) {f(s, 0);return res;}
};