代码随想录day27 回溯继续深造，新题型

39. 组合总和

题目

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

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

说明：

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

示例 1：

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

思考

这题其实和组合总和III非常像，唯一的区别是数字可以无限制重复被选取，那么startIndex就不会作为去重的参数，每次递归都从i开始即可，其余的代码与组合总和III一模一样

代码

class Solution {

public:

? ? vector<vector<int>> res;

? ? vector<int> path;

? ? void backTracking(vector<int>& candidates, int target, int sum, int startIndex) {

? ? ? ? if(sum > target) return;

? ? ? ? if(sum == target) {

? ? ? ? ? ? res.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);

? ? ? ? ? ? sum -= candidates[i];

? ? ? ? ? ? path.pop_back();

? ? ? ? }

? ? }

? ? vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

? ? ? ? backTracking(candidates, target, 0, 0);

? ? ? ? return res;

? ? }

};

40.组合总和II

题目

给定一个数组?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]
]

思考

有难度，感觉和组合总和I、III不太一样，按照卡哥的话来说，这题要树层去重，即如果横向遍历时，如果该数与上一个数重复（注意需要把原数组sort一下），那么这个数可以考虑直接跳过，同时呢，为了树枝不去重（该数与上一个数相同也可以使用），我们这里用到了used数组的概念，这个used数组非常奇妙，其实相当于一个flag数组，大小和原数组一样，刚开始全是零，即所有数都没有使用过，当遍历到末尾时，used数组里全变成1，那么这时候要进入到下一个树层进行递归，又把原先遍历过的数置为零，这样当如果该数与上一个数重复且used[i-1] == 0时，才能真正跳过，这个去重的思路非常奇妙，也很典型，需要重点掌握

代码

class Solution {

public:

? ? vector<vector<int>> res;

? ? vector<int> path;

? ? void backTracking(vector<int>& candidates, vector<int>& used, int target, int sum, int startIndex) {

? ? ? ? if(sum > target) return;

? ? ? ? if(sum == target) {

? ? ? ? ? ? res.push_back(path);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? for(int i = startIndex; i < candidates.size(); i++) {

? ? ? ? ? ? //下一行的去重逻辑是树层去重，used[i-1] == 0是要保证纵向遍历时树枝不去重

? ? ? ? ? ? if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == 0) continue;

? ? ? ? ? ? sum += candidates[i];

? ? ? ? ? ? path.push_back(candidates[i]);

? ? ? ? ? ? used[i] = 1;

? ? ? ? ? ? backTracking(candidates, used, target, sum, i+1);

? ? ? ? ? ? sum -= candidates[i];

? ? ? ? ? ? used[i] = 0;

? ? ? ? ? ? path.pop_back();

? ? ? ? }

? ? }

? ? vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

? ? ? ? vector<int> used(candidates.size(),0);

? ? ? ? sort(candidates.begin(), candidates.end());//必须sort

? ? ? ? backTracking(candidates, used, target, 0, 0);

? ? ? ? return res;

? ? }

};

131.分割回文串

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入:?"aab" 输出: [ ["aa","b"], ["a","a","b"] ]

思考

和组合不一样，这题是分割，对于我来说难点有以下几个：

1、中止条件是什么？ 因为要遍历到字符串最后一位，那么就是当startIndex == s.size()时收获借过

2、怎么收集到的字符串是否是回文？用双指针的方法来判断，及从要收集字符串头尾开始向中间遍历，如果s[i]一直等于s[j]，那么就是回文串

3、判断是回文串时如何收集？用substr(startIndex, i - startIndex + 1)

代码

class Solution {

public:

? ? vector<vector<string>> res;

? ? vector<string> path;

? ? bool isRound(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;

? ? }

? ? void backTracking(string s, int startIndex) {

? ? ? ? if(startIndex == s.size()) {//当遍历到s末尾时开始收集结果

? ? ? ? ? ? res.push_back(path);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? for(int i = startIndex; i < s.size(); i++) {

? ? ? ? ? ? if(isRound(s, startIndex, i)) {

? ? ? ? ? ? ? ? string tmp = s.substr(startIndex, i - startIndex + 1);//截取从stratIndex到i的字符串

? ? ? ? ? ? ? ? path.push_back(tmp);

? ? ? ? ? ? }

? ? ? ? ? ? else continue;

? ? ? ? ? ? backTracking(s, i+1);

? ? ? ? ? ? path.pop_back();

? ? ? ? }

? ? }

? ? vector<vector<string>> partition(string s) {

? ? ? ? backTracking(s, 0);

? ? ? ? return res;

? ? }

};