算法训练营第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;
    }
};