39. 组合总和

class Solution {
public:vector<vector<int>> result;vector<int> temp;void backtructing(vector<int>& candidates, int target, int sum,int start){if(sum==target){result.push_back(temp);return;}if(sum>target){return;}for(int i = start;i<candidates.size();i++){sum+=candidates[i];temp.push_back(candidates[i]);backtructing(candidates,target,sum,i);sum-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtructing(candidates,target,0,0);return result;}
};

思路只有值超过目标值时才会返回，i都不行才进入下一个数字。

40. 组合总和 II

class Solution {
public:vector<vector<int>> result;vector<int> temp;void backtructing(vector<int>& candidates, int target, int sum,int start){if(sum==target){result.push_back(temp);return;}if(sum>target){return;}for(int i = start;i<candidates.size();i++){if(i>start&&candidates[i]==candidates[i-1]){continue;}sum+=candidates[i];temp.push_back(candidates[i]);backtructing(candidates,target,sum,i+1);sum-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtructing(candidates,target,0,0);return result;}
};

思路这个题整体不难，就是有一些细节，每次递归需要传入+1，但是因为可能有重复元素，所以要去重，排序，然后当相邻两个元素相等说明会产生同样的组合所以continue

131. 分割回文串

class Solution {
public:vector<vector<string>> result;vector<string> temp;bool idpartition(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 backtructing(string s,int start){if(start>=s.size()){result.push_back(temp);return;}for(int i = start;i<s.size();i++){if(idpartition(s,start,i)){string str = s.substr(start,i-start+1);temp.push_back(str);}else{continue;}backtructing(s,i+1);temp.pop_back();}}vector<vector<string>> partition(string s) {backtructing (s,0);return result;}
};

关键在于，区间判断是否为回文子串