算法训练营第27天|LeetCode 39.组合总和 40.组合总和2 131.分割回文串

LeetCode 39.组合总和

题目链接：

LeetCode 39.组合总和

解题思路：

用回溯的方法，，注意这次回溯不是i+1，而是i，是因为可用重复选取。

代码：

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

LeetCode 40.组合总和2

题目链接：

LeetCode 40.组合总和2

解题思路：

用used数组看前面元素是否使用过，之后将数组排序，当和前面元素重复且前面元素没用过时，元素进行下一个，来去重。

代码：

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

LeetCode 131.分割回文串

题目链接：

LeetCode 131.分割回文串

解题思路：

将切割类比为组合问题，将元素索引变化为切割位置，逐个判断是不是回文的，之后进行回溯。

代码：

class Solution {
public: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;}vector<vector<string>> result;vector<string> path;void backtracking(string s, int Index) {if (Index >= s.size()) {result.push_back(path);return;}for (int i = Index; i < s.size(); i++) {if (isPalindrome(s, Index, i)) {path.push_back(s.substr(Index, i - Index + 1));} else {continue;}backtracking(s, i + 1);path.pop_back();}}vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};