代码随想录算法训练营第day26|39. 组合总和、 40.组合总和II、 131.分割回文串

本文主要是介绍代码随想录算法训练营第day26|39. 组合总和、 40.组合总和II、 131.分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

39. 组合总和

力扣题目链接(opens new window)

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

示例 1：

• 输入：candidates = [2,3,6,7], target = 7,
• 所求解集为： [ [7], [2,2,3] ]

示例 2：

• 输入：candidates = [2,3,5], target = 8,
• 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

思路：

本题搜索的过程抽象成树形结构如下：

 注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？如果是一个集合来求组合的话，就需要startIndex；如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}//横向遍历树结构for (int i = startIndex; i < candidates.size(); i++) {sum += candidates[i];path.push_back(candidates[i]);// 纵向遍历树结构backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数sum -= candidates[i];//回溯path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}
};

40.组合总和II

力扣题目链接(opens new window)

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

• 示例 1:
• 输入: candidates = [10,1,2,7,6,1,5], target = 8,
• 所求解集为:

[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]

• 示例 2:
• 输入: candidates = [2,5,2,1,2], target = 5,
• 所求解集为:

[[1,2,2],[5]
]

思路:

这道题目和39.组合总和 (opens new window)如下区别：

1. 本题candidates 中的每个数字在每个组合中只能使用一次。
2. 本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates

最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！

所以要在搜索的过程中就去掉重复组合。

我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）

强调一下，树层去重的话，需要对数组排序！

选择过程树形结构如图所示：

与39.组合总和 (opens new window)套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

这个集合去重的重任就是used来完成的。

前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

在candidates[i] == candidates[i - 1]相同的情况下：

• 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，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：

 

class Solution {
public:vector<int>path;vector<vector<int>>result;// int sum=0;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool> used){//终止条件if(sum==target) {result.push_back(path);return;}if(sum>target)return;//横向遍历树状结构// &&sum+candidates[i]<target是为了剪枝，剪去不必要的遍历for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){//同层去重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);//纵向遍历，递归，i+1开始，因为不可重复选择同一元素//回溯sum-=candidates[i];path.pop_back();used[i]=false;}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(), false);path.clear();result.clear();sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

9.分割回⽂串 

131. 分割回文串 - 力扣（LeetCode）

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

思路:本题这涉及到两个关键问题：

1. 切割问题，有不同的切割⽅式

2. 判断回⽂

我们来分析⼀下切割，其实切割问题类似组合问题。 例如对于字符串abcdef：

组合问题：选取⼀个a之后，在bcdef中再去选取第⼆个，选取b之后在cdef中再选取第三个.....。

切割问题：切割⼀个a之后，在bcdef中再去切割第⼆段，切割b之后在cdef中再切割第三段.....

所以切割问题，也可以抽象为⼀棵树形结构

全局变量数组path存放切割后回⽂的⼦串，⼆维数组result存放结果集。 （这两个参数可以放到函数参数⾥） 本题递归函数参数还需要startIndex，因为切割过的地⽅，不能重复切割，和组合问题也是保持⼀致的。

终止条件：切割线切到了字符串最后⾯，说明找到了⼀种切割⽅法，此时就是本层递归的终⽌条 件

class Solution {
public:vector<string>path;vector<vector<string>>result;void backtracking(string& s, int startIndex){if(startIndex>=s.size()){//递归结束条件result.push_back(path);}//横向遍历树状结构for(int i=startIndex;i<s.size();i++){if(isPalindrome(s, startIndex, i)){//判断是否为回文字符串//截取回文串string str =s.substr(startIndex, i-startIndex+1);path.push_back(str);}else continue;//纵向遍历树结构backtracking(s,i+1);path.pop_back();//回溯}}bool isPalindrome(string& s, int startIndex, int endIndex){for(int i=startIndex,j=endIndex;i<j;i++,j--){if(s[i]!=s[j]) return false;}return true;}vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s,0);return result;}
};

 

参考：代码随想录

这篇关于代码随想录算法训练营第day26|39. 组合总和、 40.组合总和II、 131.分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---