代码随想录第26天|回溯算法

参考

思路:

• 使用 sum 控制递归层数
• 目标数组可以重复使用

难点:

• 因目标数组内元素可以重复使用, 但需消除重复的组合(不同排列)
• 比如 [2,2,3][2,3,2][3,2,2]

//有效消除重复问题, 前提是输入的candidates数组没有重复元素
class Solution {
public:vector<vector<int>> res;vector<int> res_tem;void myoperator(vector<int>& candidates, int target, int sum, int index) {if (sum >= target) {if (sum == target) res.push_back(res_tem);return;}for (int i = index; i < candidates.size(); i++) {if (sum > target) break;//剪枝操作res_tem.push_back(candidates[i]);myoperator(candidates, target, sum + candidates[i], i);//此处若为 i + 1,则代表不重复元素res_tem.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());//最好进行排序,方便剪枝myoperator(candidates, target, 0, 0);return res;}
};

//错误解答, 会出现重复数组 比如 [2,2,3][2,3,2][3,2,2]
class Solution {
public:vector<vector<int>> res;vector<int> res_tem;void myoperator(vector<int>& candidates, int target, int sum) {if (sum >= target) {if (sum == target) res.push_back(res_tem);return;}for (int i =0; i < candidates.size(); i++) {if (sum > target) break;//剪枝操作res_tem.push_back(candidates[i]);myoperator(candidates, target, sum + candidates[i]);res_tem.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {myoperator(candidates, target, 0);return res;}
};

错误情况:
由于有重复元素的影响, [1,7] 和 [1,7] 其实是两个不同的1, 但不符合条件
同一树枝是结果, 是可以选择相同元素的
同一层是不同的结果, 是不可以选中相同元素的

树枝可以使用相同的元素, 但同一数层则不能使用重复的元素, 需要对其剪枝
使用一个use数组标记是否用过元素

思路:
使用 used 数组对同一层去重

used[i - 1] = 1 时, 代表的是同一树枝的情况, 此情况不应该去重
used[i - 1] = 0 时, 代表的是同一树层的情况, 此情况应该去重
由于used是经过回溯赋值的, 所以同一层的情况为: [1,0,0] [0,1,0] [0,0,1], 表示开始取数的位置
而同一树枝, [1,0,0] 和 [1,1,0], 表示用过的元素, 这种情况不排除

class Solution {
public:vector<vector<int>> res;vector<int> res_tem;void myoperator(vector<int>& candidates, int target, int sum, int index, vector<bool>&used) {if (sum >= target) {if (sum == target) res.push_back(res_tem);return;}for(int i = index; i < candidates.size(); i++) {if (sum > target) break;//[1,0,0] 和 [1,1,0] 不排除//[1,0,0] 和 [0,1,0] 排除if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;res_tem.push_back(candidates[i]);used[i] = true;myoperator(candidates, target, sum + candidates[i], i + 1, used);            res_tem.pop_back();used[i] = false;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<bool> used(candidates.size(), 0);myoperator(candidates, target, 0, 0, used);return res;}
};

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

难点:

• 对字符串的切割分析, 切割范围为 [index, i]
• 特殊情况 [0,0] 也通用
• 思路和组合题目相同, 也是选择不同的元素

class Solution {
public:vector<vector<string>> res;vector<string> res_tem;bool judge (string& s) {int left = 0, right = s.length() - 1;while (left <= right) {if (s[left] != s[right]) return false;left++;right--;}return true;}void myoperator(string& s, int index) {if (index >= s.length()) {res.push_back(res_tem);return;}for (int i = index; i < s.length(); i++) {string str(s, index, i - index + 1);if (judge(str)) {res_tem.push_back(str);} else {continue;}myoperator(s, i + 1);res_tem.pop_back();}}vector<vector<string>> partition(string s) {myoperator(s, 0);return res;}
};