day27 回溯（03）

day27
代码随想录
2023.12.25

1. 39组合总和
这道题还是组合问题，一样的代码套路，不过就是递归参数不同，数组元素可以重复，所以是i而不是i+1；其次就是终止条件，当temp的sum大于target则终止，当等于时则加入到result中;
越来明白回溯本质就是穷举了，就是试探所有可能得组合，等有满足要求的，添加到结果中即可。

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

2. 40组合总和Ⅱ
乍一看以为一样，细看后发现，首先，不允许重复使用，所以递归参数是i+1，其次也是本题的关键，数组中会出现重复数字，但是结果不允许出现重复，因此在第一层递归中，遇到相同的值就要越过，这里要注意是递归中，该层相同的要跳过，如果是深度往下递归值相同，则不用跳过，在开始对数据进行排序，这样相同值就相邻了，然后递归判断前后相同不，相同就跳过，

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

            temp.push_back(candidates[i]);
            backtravel(candidates,target,i+1);
            temp.pop_back();
      
        }
    }
};

在跳过相同的判断中i>index就是将同层没有相同的，如果是i>0，则是将所有相同元素都越过了

3. 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> temp;
    vector<vector<string>> partition(string s) {
        backtravel(s,0);
        return result;
    }
    void backtravel(string& s, int index){
        if (index == s.size()) {
        result.push_back(temp);
        return;
    }
        
        for (int i = index; i < s.size(); i++) {
            if (isPalindrome(s, index, i)) {
                temp.push_back(s.substr(index, i - index + 1));
                backtravel(s, i + 1);
                temp.pop_back();
            }
        }
    }
};