合肥网站网站建设,重庆施工员证查询网站,百度蜘蛛池自动收录seo,ceac网页设计师证书如何考组合问题#xff1a;集合内元素的组合#xff0c;不同集合内元素的组合 分割问题#xff1a;本质还是组合问题#xff0c;注意一下如何分割字符串 回溯模板伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本层集合中元素#xf… 组合问题集合内元素的组合不同集合内元素的组合 分割问题本质还是组合问题注意一下如何分割字符串 回溯模板伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
关键点
无重复元素、集合内同一元素可以重复选取
思路
仍然是一个集合内元素的组合问题 可以重复是指可以选取下一层子集包含上层取的元素上层所取元素其右边所有元素所以backtracking(candidates, target, i)是i而非i1
横向遍历是针对当前集合遍历该集合的所有元素纵向遍历是针对取后得到的当前集合的子集下一层子集包含上层取的元素上层所取元素其右边所有元素
代码
class Solution {
public:vectorvectorint result;vectorint path;int sum 0;void backtracking(vectorint candidates, int target, int startIndex) {if(sum target) return;if(sum target) {result.push_back(path);return;}for(int i startIndex; i candidates.size(); i) {//if(sum candidates[i] target) return;sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, i); //可以重复选取所以是i而非i1// 可以重复是指可以选取下一层子集包含上层取的元素上层所取元素其右边所有元素sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sum 0;backtracking(candidates, target, 0);return result;}
};40.组合总和II
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。
关键点
集合内有重复的元素 集合内同一元素不能被重复选取
思路
元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同——去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。
横向遍历是针对当前号码对应的字符集遍历该字符集的所有元素纵向遍历是针对下一个号码对应的字符集合遍历下一个字符集 而不是当前字符集的子集 下图是用数组来标注同一树层的元素是否被已被使用进而来对树层去除
class Solution {
public:vectorvectorint result;vectorint path;int sum 0;void backtracking(vectorint candidates, int target, int startIndex) {if(sum target) return;if(sum target) {result.push_back(path);return;}for(int i startIndex; i candidates.size(); i) {// 要对同一树层使用过的元素进行跳过同树枝的相同元素可以选取if(i startIndex candidates[i] candidates[i-1]) continue; // 集合存在相同元素,要避免结果重复sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, i1); //不可以重复选取所以是i1// 集合存在相同元素sum - candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {result.clear();path.clear();sum 0;sort(candidates.begin(), candidates.end()); //排序使相同元素连续backtracking(candidates, target, 0);return result;}
};131.分割回文串
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。
关键点
回文串的判断 集合内同一元素不能被重复选取
思路
本质是一个组合问题集合内同一元素不能被重复选取
横向遍历是针对当前字符集遍历该字符集的所有元素纵向遍历是针对截取得到的字符集合且集合内同一元素不能被重复选取
class Solution {
public:vectorvectorstring result;vectorstring path;bool IsPalindrome(const string s, int start, int end) {while(start end) {if(s[start] ! s[end--]) return false; //从首尾对应比较有一次不等即非回文}return true;}void backtracking(const string s, int startIndex) {if(startIndex s.size()) {result.push_back(path);return;}for(int i startIndex; i s.size(); i) {bool flag false;if(IsPalindrome(s, startIndex, i)) {string str s.substr(startIndex, i - startIndex 1); path.push_back(str);flag true;} else{continue;}backtracking(s, i1); // 寻找i1为起始位置的子串因为字符串内字符不能重复选取if(flag) {path.pop_back();}}}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};优化思路
动态规划得到所有可能得到的子串并判断其是否为回文串然后回溯过程中判断是否回文串可以直接查数组。
