前言

 回溯是什么？

 

题目链接

 39. 组合总和 - 力扣（LeetCode）

40. 组合总和 II - 力扣（LeetCode）

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

一、组合问题

 

    private:vector<vector<int>>res;vector<int> path;void backtracking(vector<int>&candidates,int target,int sum,int startIndex){if(sum==target){res.push_back(path);return ;}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:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {res.clear();path.clear();sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return res;}

二、组合问题

 

 

vector<vector<int>>res;vector<int>path;void backtracking(vector<int>&candidates,int target,int sum,int startIndex){if(sum==target) {res.push_back(path);return;}for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){if(i>startIndex&&candidates[i]==candidates[i-1])continue;sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return res;}

三、分割回文串

 

 

    vector<vector<string>> res;vector<string>path;void backtracking(const string&s,int startIndex){if(startIndex>=s.size()){res.push_back(path);return ;}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(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:vector<vector<string>> partition(string s) {backtracking(s,0);return res;}

总结