代码随想录算法训练营第30天

标签：target int 训练营 30 随想录 vector candidates result sum

今日刷题3道：39. 组合总和，40.组合总和II，131.分割回文串

●  39. 组合总和

题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ

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

●  40.组合总和II

题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html

视频讲解：https://www.bilibili.com/video/BV12V4y1V73A

class Solution { private:     vector<vector<int>> result;     vector<int> path;     void backtracking(vector<int>& candidates, int sum, int target, int index, vector<bool>& 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] == false){                 continue;             }             sum+=candidates[i];             path.push_back(candidates[i]);             used[i]=true;             backtracking(candidates,sum,target,i+1,used);             used[i]=false;             sum-=candidates[i];             path.pop_back();         }     } public:     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {         vector<bool> used(candidates.size(),false);         sort(candidates.begin(),candidates.end());         backtracking(candidates,0,target,0, used);         return result;     } };  

●  131.分割回文串

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6

 

class Solution { private:     vector<vector<string>> result;     vector<string> path;     void backtracking(const string& s, int startIndex){         if(startIndex >= s.size()){             result.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 result;     } };

标签：target,int,训练营,30,随想录,vector,candidates,result,sum
From： https://www.cnblogs.com/zzw0612/p/17067204.html