代码随想录第23天|回溯part3 组合与分割

39.组合总和

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& candidates,int target,int sum,int n,int step){if(n > 150) return;if(sum > target) return;if(sum == target){res.push_back(path);return;}for(int i = step; i < candidates.size(); i++){path.push_back(candidates[i]);backTracking(candidates,target,sum+candidates[i],n+1,i);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backTracking(candidates,target,0,0,0);return res;}
};

40.组合总和2

难题

可以看出在candidates[i] == candidates[i - 1]相同的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过
因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上

即：因为在排序后，相同的数都会挨在一起，如果当前数和上个数相同的话，那么在递归的过程中，如果上一个数没被用到，那么当前数肯定是一种重复的情况，因为这两个数相同，肯定是先使用前一个数的，而如果上一个没用到，则表示是已经递归过上一个数的所有情况并回溯了，现在递归下一个数的，所以需要跳过重复的这个数。

class Solution {
public:vector<vector<int>> res;vector<int> path;bool used[101];void backTracking(vector<int>& candidates, int target, int sum, int step) {if (sum == target) {res.push_back(path);return;}for (int i = step; i < candidates.size(); i++) {if (sum + candidates[i] > target)break;if (i > 0 && used[i - 1] == false &&candidates[i] == candidates[i - 1])continue;path.push_back(candidates[i]);used[i] = true;backTracking(candidates, target, sum + candidates[i], i + 1);used[i] = false;path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());backTracking(candidates, target, 0, 0);return res;}
};

也可以直接使用startIndex来去重，每层递归里，如果一个数和上一个数相同，则跳过

void backtracking(vector<int>& 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++) {// 要对同一树层使用过的元素进行跳过// 这里i > startIndex是为了确保可以选取到同一种元素，在下层递归的时候，因为传入的是i+1，所以如果i+1和上一个元素相同，递归后也可以选取和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，这里是i+1，每个数字在每个组合中只能使用一次sum -= candidates[i];path.pop_back();}}

131.分割回文串

回溯三步
1.递归函数确定参数：string s, int step
2.确定终止条件：因为分割串类似于组合问题，
例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

返回条件就是，当切割点超过串的长度时，说明已经找到一种每个字串都是回文串的方案了，这个时候就可以把字串数组传给结果
3.确定单层逻辑
单层逻辑就是树的横向遍历，即用for循环确定切割点，且切割点必须不断往后

class Solution {
public:vector<vector<string>> res;vector<string> path;bool check(string t) {for (int i = 0, j = t.size() - 1; i < j; i++, j--) {if (t[i] != t[j])return false;}return true;}void backTracking(string s, int step) {if (step >= s.size()) {// 如果大于数组长度，则找到一组全为回文串的字串组合，否则被continue掉了res.push_back(path);return;}for (int i = step; i < s.size(); i++) {// 截取字串string t = s.substr(step, i - step + 1);// 找到了符合条件的字串if (check(t))path.push_back(t);elsecontinue;// 进行下一层递归backTracking(s, i + 1);path.pop_back();}}vector<vector<string>> partition(string s) {backTracking(s, 0);return res;}
};

最近在学go，所以提供一个go版本的代码

var res [][]string
var path []stringfunc check(t string) bool {for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {if t[i] != t[j] {return false}}return true
}
func backTracking(s string, step int) {if step >= len(s) {temp := make([]string, len(path))copy(temp, path)res = append(res, temp)return}for i := step; i < len(s); i++ {t := s[step : i+1]if check(t) {path = append(path, t)} else {continue}backTracking(s, i+1)path = path[:len(path)-1]}
}
func partition(s string) [][]string {path = make([]string, 0)res = make([][]string, 0)backTracking(s, 0)return res
}