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

39 组合总和class Solution { public: void backtracking(int sum,int target,vectorint candidates,vectorvectorint result,vectorint 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; } } vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorint result; vectorint path; int sum 0; int index 0; backtracking(sum,target,candidates,result,path,index); return result; } };40 组合总和 IIclass Solution { public: void backtracking(int sum,int target,vectorint candidates,vectorvectorint result,vectorint path,int index,vectorint 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; } } vectorvectorint combinationSum2(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); vectorint used(candidates.size(), 0); vectorvectorint result; vectorint 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(leftright){ if(s[left] ! s[right]) return false; left; right--; } return true; } void backtracking(int index,string s,vectorvectorstring result,vectorstring 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(i1,s,result,path); path.pop_back(); } } vectorvectorstring partition(string s) { vectorstring path; vectorvectorstring result; backtracking(0,s,result,path); return result; } };