第二十七天| 39. 组合总和 、40.组合总和II、131.分割回文串

Leetcode 39. 组合总和

题目链接：39 组合总和

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

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

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

• candidates 的所有元素 互不相同

思考：和leetcode 77. 组合几乎相似，区别在于数组中的数字可以无限次数选取，则只需要将单层搜索逻辑中递归处理中传递的参数startIndex改为i，这样同一数字可重复取。加上剪枝处理，单层搜索逻辑中若当前处理数字加上sum大于目标值target则此数字不进入递归处理。

代码：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i< candidates.size(); i++) {
            if (sum + candidates[i] > target)       //剪枝
                continue;
            path.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, sum, i);       //当前数字可重复取
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

Leetcode 40.组合总和II

题目链接：40 组合总和II

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

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

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

思考：和上题的区别：

• 本题candidates 中的每个数字在每个组合中只能使用一次。
•  本题数组candidates的元素是有重复的，而上题是无重复元素的数组candidates

把所有组合求出来，再用set或者map去重，这么做很容易超时。因此：

• 首先单层搜索逻辑中的递归传参startIndex改为i + 1，数字不重复取
• 其次延申路径时注意同一层次取数 数组中重复的元素只取一次（相同的元素前面处理过）

代码：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i< candidates.size(); i++) {
            //去重，同一层相同的元素只用第一个
            if (i > startIndex && candidates[i] == candidates[i - 1])
                continue;

            if (sum + candidates[i] > target)       //剪枝
                continue;
            path.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, sum, i + 1);       //当前数字可重复取
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end());     //排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

Leetcode 131.分割回文串

题目链接：131 分割回文串

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

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

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

思考：

切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。可以用递归参数startIndex来表示切割线。

单层搜索逻辑：for循环中定义起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。先判断这个子串是不是回文，如果是回文，就加入在加入容器path中，path用来记录切割过的回文子串。再递归处理，最后回溯移除字符串。

判断回文逻辑：双指针法。前后两指针分别指头尾进行比较，若两字符出现不相等则不为回文。

代码：

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;
    void backtracking(const string& s, int startIndex) {
        if (startIndex >= s.size()) {       //起始位置大于字符串大小则说明以及找到一套方案
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.push_back(s.substr(startIndex, i - startIndex + 1));
                backtracking(s, i + 1);     //从i + 1处开始找回文
                path.pop_back();        //回溯
            }
        }

    }

    //判断是否为回文
    bool isPalindrome(const string& s, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--)
            if (s[i] != s[j])   return false;
        return true;
    }

    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};

自我总结：

• 理解回溯法分割线startIndex的用处