代码随想录算法训练营第23期day26|39. 组合总和、40.组合总和II、131.分割回文串

目录

一、（leetcode 39）组合总和

二、（leetcode 40）组合总和II

三、（leetcode 131）分割回文串

---

一、（leetcode 39）组合总和

力扣题目链接

状态：基本回溯AC，剪枝优化未AC。

基本的回溯方法遵循回溯模板，需要注意的是回溯中的startIndex是从当前i继续而不是i+1，因为组合中的数字允许重复。剪枝优化的思路是通过target这个限制条件。在基本回溯的过程中，终止条件是当前层的sum大于target，但如果之后的数比当前数大，那么后续的递归是多余的。因此可以同通过先排序，再防止进入大于target下一层的操作来进行剪枝优化。

class Solution {
public:
    vectorint>> res;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex){
        if(sum == target){
            res.emplace_back(path);
            return;
        }
 
        int len =candidates.size();
        for(int i = startIndex; i < len && sum + candidates[i] <= target; ++i){
            sum += candidates[i];
            path.emplace_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vectorint>> combinationSum(vector<int>& candidates, int target) {
        res.clear();
        path.clear();
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return res;
    }
};

二、（leetcode 40）组合总和II

力扣题目链接

状态：查看思路后AC。

这题乍一看和上一题一样，无非就是同一个元素不能重复使用，似乎只要将层中的递归startIndex修改为i+1即可。但是这道题还有另一个难点，那就是数组中会出现重复的元素，同一位置的元素不能重复使用，同时最终答案也不能出现重复path，这就是一个判断树层去重（而不是树枝去重）的过程，为此加入一个used数组作为辅助判断。时间复杂度，空间复杂度。

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

这道题也可以不用used数组，直接判断与前一个位置相同的元素的下标是否是本身，即

if(i > startIndex && candidates[i] == candidates[i-1]) continue;

三、（leetcode 131）分割回文串

力扣题目链接 

状态：有思路但是没有代码实现，动态规划判断回文没想到。

这道题的主要步骤可以拆分成两个部分，如何分割和如何判断。如何分割其实就是组合问题，我们需要对每个组合进行判断，很自然地想到了回溯方法来进行穷举；至于如何判断，想到的第一种方法就是双指针一左一右进行判断（还有利用栈的特性，不过不比双指针效率高）。可以优化的部分就是利用动态规划对回文串进行判断，一个回文串的去两端子串也一定是回文串。但是实际的代码编写，还需要练习。主要难点如下：

• 切割问题可以抽象为组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文

class Solution {
public:
    vector> res;
    vector path;
    vectorbool>>isPalindrome; // dp数组
    void backtracking(const string& s, int startIndex){
        if(startIndex >= s.size()){
            res.emplace_back(path);
            return;
        }
        int len = s.size();
        for(int i = startIndex; i < len; ++i){
            if(isPalindrome[startIndex][i]){
                string str = s.substr(startIndex, i-startIndex+1);
                path.emplace_back(str);
            }else{
                continue;
            }
            backtracking(s, i+1);
            path.pop_back();
        }
    }
    void computePalindrome(const string& s){
        int len = s.size();
        isPalindrome.resize(len, vector<bool>(len, false));
        for(int i = len-1; i >= 0; --i){
            for(int j = i; j < len; ++j){
                if(j == i){
                    isPalindrome[i][j] = true;
                }else if(j - i == 1){
                    isPalindrome[i][j] = (s[i] == s[j]);
                }else{
                    isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);
                }
            }
        }
    }
    vector> partition(string s) {
        res.clear();
        path.clear();
        computePalindrome(s);
        backtracking(s, 0);
        return res;
    }
};