手机移动网站模板,网站建设与管理期末总结,西安seo外包行者seo06,海洋网络39 组合总和#xff08;medium#xff09;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates…39 组合总和medium
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
思路回溯法模版可以利用排序进行剪枝
代码实现
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);return;}// 如果 sum candidates[i] target 就终止遍历for (int i startIndex; i candidates.size() sum candidates[i] target; i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);sum - candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end()); // 需要排序backtracking(candidates, target, 0, 0);return result;}
};详细解析 思路视频 代码实现文章 40 组合总和IImedium
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
思路回溯法关键在于去重操作分清树层去重和树枝去重
本题的难点在于集合数组candidates有重复元素但还不能有重复的组合。而把所有组合求出来再用set或者map去重很容易超时
所以要在搜索的过程中就去掉重复组合。
都知道组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。
那么问题来了我们是要同一树层上使用过还是同一树枝上使用过呢
回看一下题目元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。
为了理解去重我们来举一个例子candidates [1, 1, 2], target 3
选择过程树形结构如图所示 递归函数参数
与39.组合总和套路相同此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。
代码如下
vectorvectorint result; // 存放组合集合
vectorint path; // 符合条件的组合
void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {递归终止条件
与39.组合总和相同终止条件为 sum target 和 sum target。
代码如下
if (sum target) { // 这个条件其实可以省略return;
}
if (sum target) {result.push_back(path);return;
}sum target 这个条件其实可以省略因为在递归单层遍历的时候会有剪枝的操作下面会介绍到。
单层搜索的逻辑
这里与39.组合总和最大的不同就是要去重了。
前面我们提到要去重的是“同一树层上的使用过”如何判断同一树层上元素相同的元素是否使用过了呢。
如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。
used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过
为什么 used[i - 1] false 就是同一树层呢因为同一树层used[i - 1] false 才能表示当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] true说明是进入下一层递归去下一个数所以是树枝上如图所示
那么单层搜索的逻辑代码如下
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这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();
}注意sum candidates[i] target为剪枝操作在39.组合总和有讲解过
代码实现1used数组去重
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool 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这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};
代码实现2直接用startIndex去重
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// 要对同一树层使用过的元素进行跳过if (i startIndex candidates[i] candidates[i - 1]) {continue;}sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i 1); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
};
详细解析 思路视频 代码实现文章 131 分割回文串medium
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串。返回 s 所有可能的分割方案。
思路回溯法应用在分割上
本题这涉及到两个关键问题
切割问题有不同的切割方式判断回文
这种题目想用for循环暴力解法可能都不那么容易写出来所以要换一种暴力的方式就是回溯。
我们来分析一下切割其实切割问题类似组合问题。
例如对于字符串abcdef
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个…。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段…。
所以切割问题也可以抽象为一棵树形结构如图 递归用来纵向遍历for循环用来横向遍历切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。
此时可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
递归函数参数
全局变量数组path存放切割后回文的子串二维数组result存放结果集。 这两个参数可以放到函数参数里
本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。
代码如下
vectorvectorstring result;
vectorstring path; // 放已经回文的子串
void backtracking (const string s, int startIndex) {递归函数终止条件
从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。
那么在代码里什么是切割线呢
在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。
所以终止条件代码如下
void backtracking (const string s, int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.size()) {result.push_back(path);return;}
}单层搜索的逻辑
来看看在递归循环中如何截取子串呢
在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文如果是回文就加入在vectorstring path中path用来记录切割过的回文子串。
代码如下
for (int i startIndex; i s.size(); i) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else { // 如果不是则直接跳过continue;}backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经添加的子串
}注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。
代码实现
class Solution {
private:vectorvectorstring result;vectorstring path; // 放已经回文的子串void backtracking (const string s, int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.size()) {result.push_back(path);return;}for (int i startIndex; i s.size(); i) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else { // 不是回文跳过continue;}backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经添加的子串}}bool isPalindrome(const string s, int start, int end) {for (int i start, j end; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;}
public:vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};详细解析 思路视频 代码实现文章
