代码随想录算法训练营第二十七天 | 39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和

题目链接：39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

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

思路

这道题目和之前做过的组合III比较类似，只不过这里是允许将元素重复加入组合的。利用回溯三部曲来分析。

第一步，确定回溯函数的参数，我们需要指定当前已有元素的组合path，当前已经遍历到的下标starti，组合中元素和与target的差值left。

第二步，确定什么时候回溯结束，在这里，因为元素可以重复添加，因此判断依据是left = 0。

第三步，遍历的过程。横向遍历的过程主要是按序遍历这个整数数组candidates，纵向遍历的过程则是递归遍历组合的下一个待添加元素。需要注意的是，因为题目允许组合中有重复元素，因此我们在递归遍历组合下一个元素时，下标不需要+1。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        backtracing(path, 0, target, candidates);
        return results;
    }

    void backtracing(vector<int>& path, int starti, int left, const vector<int>& candidates){
        if(left == 0){
            results.push_back(path);
            return;
        }
        for(int i = starti;i<candidates.size();i++){
            int cur = candidates[i];
            if(cur <= left){
                path.push_back(cur);
                backtracing(path, i, left - cur, candidates);
                path.pop_back();
            }
        }
    }
};

40.组合总和II

题目链接：40.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

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

思路

这道题中要求数组中的每个元素只能使用一次，而且组合不能重复。注意，不同元素中可能数值相同。

为了便于去重，我们先将candidates数组排序，然后利用回溯三部曲来分析解决，其中去重操作可以参考之前三数之和中的方法。

第一步，确定回溯函数的参数，我们需要指定当前已有元素的组合path，当前已经遍历到的下标starti，组合中元素和与target的差值left。

第二步，何时结束回溯，当left等于0的时候。

第三步，遍历过程，横向遍历的过程主要是按序遍历这个整数数组candidates，纵向遍历的过程则是递归遍历组合的下一个待添加元素。这里在递归遍历下一个元素时，需要将下标+1。参考三数之和中的去重方法，我们在横向遍历的过程中，如果当前下标的元素和上一个下标的元素值相同，则跳过该元素，因为此时获得的组合结果一定是重复的。另外，因为我们已经将candidates数组排好了序，在横向遍历时，如果candidates[i] > left，就可以提前剪枝。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        backtracing(path, 0, target, candidates);
        return results;
    }

    void backtracing(vector<int>& path, int starti, int left, const vector<int>& candidates){
        if(left == 0){
            results.push_back(path);
            return;
        }

        for(int i = starti;i<candidates.size() && candidates[i] <= left;i++){
            if(i > starti && candidates[i] == candidates[i - 1]) continue;
            path.push_back(candidates[i]);
            backtracing(path, i + 1, left - candidates[i], candidates);
            path.pop_back();
        }
    }
};

131.分割回文串

题目链接：131.分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

文章讲解/视频讲解：https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

思路

采用回溯的三部曲来解决。

首先确定回溯函数的参数值，我们需要一个存储当前回文串数组的集合path，当前已经遍历到的下标starti。

什么时候回溯停止？当starti等于字符串s的长度时，表面当前已经遍历到了s的末尾。此时，需要做一个判断，如果path中所有回文串的长度等于s的长度，即path把s中的所有元素都包括了，那么我们就找到了一种回文串划分，并将这个划分添加进结果中。

如何遍历？我们每次回溯的目标是找到一种划分，这种划分得到的所有子串都是回文子串。横向遍历的过程是找到划分中当前的分隔，纵向遍历的过程是找到下一个分隔。怎么去找这样的分隔呢？我们需要在横向遍历的时候采用两层遍历，i指向当前分隔的起点，j指向当前分隔的终点。如果i, j之间能够构成一个回文串，则继续纵向遍历下一个分隔，此时将starti设置为j + 1。

C++实现

class Solution {
public:
    vector<vector<string>> results;
    vector<vector<string>> partition(string s) {
        vector<string> path;
        backtracing(path, 0, s);
        return results;
    }

    void backtracing(vector<string>& path, int starti, const string& s){
        if(starti == s.size()){
            int length_sum = 0;
            for(int i = 0;i<path.size();i++) length_sum += path[i].size();
            if(length_sum == s.size()) results.push_back(path);
            return;
        }

        for(int i = starti;i<s.size();i++){
            for(int j = i;j<s.size();j++){
                if(isPalindrome(s, i, j)){
                    string cur = s.substr(i, j - i + 1);
                    path.push_back(cur);
                    backtracing(path, j + 1, s);
                    path.pop_back();                    
                }
            }
        }
    }

    bool isPalindrome(const string& s, int left, int right){
        while(left < right){
            if(s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};