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

算法刷题Day27 | 39. 组合总和、40.组合总和II、131.分割回文串

news 来源：原创 2024/5/17 4:45:42

0 引言

趁着周末赶紧追

1 组合总和

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

1.1 我的解题

这道题其实就是可以把已经遍历的元素再遍历一次，就是改变了 firstIndex 的位置而已。逻辑和之前的题目类似。还有终止条件不太一样就是。

class Solution
{
public:// 1. 回溯函数参数和返回值void backTracing(vector<int>& candidates, int target, int firstIndex, vector<int>& path, vector<vector<int>>& paths){// 2. 终止条件int sum = 0;for (auto data : path){sum += data;}if (sum > target){return;}if (sum == target){paths.emplace_back(path);return;}// 3. 单层回溯逻辑for (int i = firstIndex; i < candidates.size(); i++){path.emplace_back(candidates[i]);backTracing(candidates, target, i, path, paths);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> paths;vector<int> path;backTracing(candidates, target, 0, path, paths);return paths;}};

2 组合总和II

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

2.1 解题

这道题注意了，集合中不能有重复的。上一道题简单的改变 firstIndex 就可以避免重复的组合是因为，给出的集合中本身不含有重复的数字。但是这道题中是包含重复数字的。

这道题比较难，理解关键点在于去重：树层去重、树枝去重。

那么如何判断当前是同一层还是树枝呢？使用一个额外的 used 数组来标识。

详细的解释参考文档。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

3 分割回文串

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

3.1 切割

使用回溯进行切割是如何进行的呢？如何切割是回溯的一种经典题目了。

犀利糊涂写出来了，有一个疑惑的地方，在判断当前子串不是回文串时，为什么是进入下一个循环而不是跳出所有循环。

因为同一个循环内是同一层，加入当前层的前面有一个节点不满足，直接break的话，后面满足的节点也会被去除。所以应该使用continue。continue是跳过当前的节点，也就是说以这个节点为根的所有结果肯定都是不满足的。

class Solution {
public:// 判断是否是回文串bool isPalindrome(string s){for (int i = 0; i < s.size()/2; i++){if (s[i] != s[s.size() - 1 - i]){return false;}}return true;}// 回溯 (startIndex从0开始)void backTracing(string& s, int startIndex, vector<string>& path, vector<vector<string>>& paths){// 终止条件if (startIndex == s.size()){paths.emplace_back(path);return;}// 单层回溯逻辑for (int i = startIndex; i < s.size(); i++){string tmp = s.substr(startIndex, i - startIndex + 1);if (isPalindrome(tmp)){path.emplace_back(tmp);backTracing(s, i + 1, path, paths);path.pop_back();}else{continue;	// 注意是continue ，而不是break}}}vector<vector<string>> partition(string s) {vector<string> path;vector<vector<string>> paths;backTracing(s, 0, path, paths);return paths;}
};