网站建设功能列表,新的南宁网站建设公司,济南住建局官方网站,全国大学生创业网登录入口目录
LeetCode: 39. 组合总和
基本思路
C代码
LeetCode: 40.组合总和II
基本思路
C代码
LeetCode: 131.分割回文串
基本思路
C代码 LeetCode: 39. 组合总和 力扣代码链接 文字讲解#xff1a;LeetCode: 39. 组合总和 视频讲解#xff1a;带你学透回溯算法-组合总和…目录
LeetCode: 39. 组合总和
基本思路
C代码
LeetCode: 40.组合总和II
基本思路
C代码
LeetCode: 131.分割回文串
基本思路
C代码 LeetCode: 39. 组合总和 力扣代码链接 文字讲解LeetCode: 39. 组合总和 视频讲解带你学透回溯算法-组合总和 基本思路 本题没有数量要求可以无限重复但是有总和的限制所以间接的也是有个数的限制。将搜索过程抽象为以下树形结构 递归函数参数 这里依然是定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。 参数包括给定的集合candidates, 和目标值target还定义了int型的sum变量来统计单一结果path里的总和以及设置for循环起始位置的startIndex。
vectorvectorint result;
vectorint path;
void backtracking(vectorint candidates, int target, int sum, int startIndex)
递归终止条件 终止只有两种情况sum大于target和sum等于target。sum等于target的时候需要收集结果。
if (sum target) {return;
}
if (sum target) {result.push_back(path);return;
}
单层搜索的逻辑 单层for循环依然是从startIndex开始搜索candidates集合。
for (int i startIndex; i candidates.size(); i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 关键点:不用i1了表示可以重复读取当前的数sum - candidates[i]; // 回溯path.pop_back(); // 回溯
}
剪枝优化 对于sum已经大于target的情况其实是依然进入了下一层递归只是下一层递归结束判断的时候会判断sum target的话就返回。其实如果已经知道下一层的sum会大于target就没有必要进入下一层递归了。那么可以在for循环的搜索范围上做做文章了。 对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。 所以我们对for循环的剪枝如下
for (int i startIndex; i candidates.size() sum candidates[i] target; i)
C代码
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;}
};
LeetCode: 40.组合总和II 力扣代码链接 文字讲解LeetCode: 40.组合总和II 视频讲解回溯算法中的去重树层去重树枝去重你弄清楚了没 基本思路 这个题和上个题主要存在两个不同点本题中candidates 中的每个数字在每个组合中只能使用一次以及本题数组candidates的元素是有重复的而上一题是无重复元素的数组candidates 如果我们还按照上一题的方法就极有可能会获得重复的结果那么我们应该怎么对结果进行去重呢都知道组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。 另外我们在树层去重的时候要对数组进行排序。
递归函数参数
此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。
vectorvectorint result; // 存放组合集合
vectorint path; // 符合条件的组合
void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used)
递归终止条件 终止条件为 sum target 和 sum target。
if (sum target) { // 这个条件其实可以省略return;
}
if (sum target) {result.push_back(path);return;
}
单层搜索的逻辑 如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。 我在图中将used的变化用橘黄色标注上可以看出在candidates[i] candidates[i - 1]相同的情况下
used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过 这一块的去重逻辑很抽象一定要好好思考或者去听视频讲解去理解其中的含义。
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();
}
C代码
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;}
};LeetCode: 131.分割回文串 力扣代码链接 文字讲解LeetCode: 131.分割回文串 视频讲解带你学透回溯算法-分割回文串 基本思路 我们来分析一下切割其实切割问题类似组合问题。 例如对于字符串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。 当然我们需要一个判断是否为回文子串的函数很容易想到前面提到过的双指针法。 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;}
C代码
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;}
};
