代码随想录打卡 第二十一天

39 组合总和

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

40 组合总和 II

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

131 分割回文串

class Solution { public: bool check(string s,int left,int right){ while(left<right){ if(s[left] != s[right]) return false; left++; right--; } return true; } void backtracking(int index,string s,vector<vector<string>>& result,vector<string> path){ if(index >= s.size()){ result.push_back(path); return; } for(int i = index;i < s.size();i++){ if(check(s,index,i)){ string sub = s.substr(index, i - index + 1); path.push_back(sub); }else continue; backtracking(i+1,s,result,path); path.pop_back(); } } vector<vector<string>> partition(string s) { vector<string> path; vector<vector<string>> result; backtracking(0,s,result,path); return result; } };