代码随想录算法训练营
Day23代码随想录算法训练营第 23 天 |LeetCode 39. 组合总和 LeetCode 40.组合总和II LeetCode131.分割回文串
目录
前言
LeetCode39. 组合总和
LeetCode40.组合总和II
LeetCode131.分割回文串
一、基础
1、回溯可以看成N叉树
树的高度是递归深度，每一个树枝是一个路径（组合）
树的宽度是for循环遍历，选择不同的起点
2、去重
注意是不能出现重复的组合还是组合里不能出现重复的元素
不能出现重复组合：在选择起点时，不能选取重复的数字，因为一旦起点数字相同，选出来的组合就是相同的，所以每次for循环都要检查现在起点是否出现过
二、LeetCode 39. 组合总和
1.题目链接
2.思路
3.题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
int sum = 0;
void select(vector<int>& candidates, int target, int start) {
if (sum > target)
return;
if (sum == target) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
path.push_back(candidates[i]);
sum += candidates[i];
select(candidates, target, i);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
select(candidates, target, 0);
return res;
}
};
三、LeetCode 40.组合总和II
1.题目链接
2.思路
（1）candidates先排序
（2）去重：
candidates里面有重复数字，同一个组合里可以有重复的元素，但是不能有重复的组合
1）所以同一条路径，也就是同一个树枝上不用去重，即每次递归不用判断元素是否使用过
2）在选择起点时，不能选取重复的数字，因为一旦起点数字相同，选出来的组合就是相同的，所以每次for循环都要检查现在起点是否出现过
3.题解
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<bool> used;
int sum = 0;
void select(vector<int>& candidates, int target, int start) {
if (sum > target)
return;
if (sum == target) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (i > 0 && candidates[i] == candidates[i - 1] &&
used[i - 1] == false)
continue;
path.push_back(candidates[i]);
sum += candidates[i];
used[i] = true;
select(candidates, target, i + 1);
sum -= candidates[i];
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
for (int i = 0; i < candidates.size(); i++) {
used.push_back(false);
}
sort(candidates.begin(), candidates.end());
select(candidates, target, 0);
return res;
}
};
四、LeetCode131.分割回文串
1.题目链接
2.思路
主要分为两步：分割和回文串判定
（1）分割：递归
1）参数：字符串，分割子串的起点下标
2）边界：起点下标达到s.size()
3）单层递归：
① 遍历确定分割子串的终点下标（分割子串看作左闭右闭）
② 先判定子串是否为回文串
③ 如果是
- 那么用s.substr(起点，终点）获取子串（substr参数是左闭右开）
- 回文子串加入path（组合）
- 递归，新起点为当前终点+1
- 回溯
（2）双指针判断回文字符串
3.题解
class Solution {
public:
vector<vector<string>> res;
vector<string> path;
bool huiwen(string s, int l, int r) {
while (l < r) {
if (s[l] != s[r])
return false;
l++;
r--;
}
return true;
}
void cut(string s, int start) // start是在下标start的元素的前边进行切割
{
if (start == s.size()) {
res.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) // 从起点开始，遍历寻找子串终点
{
if (huiwen(s, start, i)) {
string str = s.substr(start, i - start + 1);
path.push_back(str);
cut(s, i + 1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
cut(s, 0);
return res;
}
};
总结
回溯可以看成N叉树
树的高度是递归深度，每一个树枝是一个路径（组合）
树的宽度是for循环遍历，选择不同的起点