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

39.组合总和

代码随想录链接

题目

LeetCode-39.组合总和

给定一个没有重复元素的数组, 在可重复选取元素的情况下, 返回所有之和等于目标值的组合, 组合与组合之间包含的不同数字的个数必须是不同的.

自己的想法

就模板题, 按照回溯法总结的模板就可以.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> current;
    int sum = 0;
    void backtracing(vector<int> &candidates, int target, int startIndex) {
        if (sum >= target) {
            if (sum == target) result.push_back(current);       // 满足之和等于目标值就记录下来
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            current.push_back(candidates[i]);
            backtracing(candidates, target, i);                 // 由于可以重复选取已经选过的值, startIndex的传参为i
            sum -= candidates[i];
            current.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracing(candidates, target, 0);
        return this -> result;
    }
};

40.组合总和II

代码随想录链接

题目

LeetCode-40.组合总和II

和上题类似, 不过可以出现重复元素, 且不同位置的元素只能被选中一次.

自己的想法

直接把上题的答案拿过来是不行的, 因为要考虑位置不同的相同元素在回溯时会产生的相同组合.

可以将相同的元素排在一起, 也就是排序, 然后再通过额外的变量, 保证两个相同的元素只出现一次时, 只考虑一遍情况.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> current;
    int sum = 0;
    void backtracing(vector<int> &candidates, int target, int startIndex, vector<bool> &used) {
        if (sum > target)   return;
        if (sum == target) {
            result.push_back(current);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;  // 如果和左侧的值相同, 且左侧的值未被使用, 代表当前处理的情况和左侧值被选中但本位置的值未被选中的情况相同, 不应再重复考虑

            sum += candidates[i];
            used[i] = true;
            current.push_back(candidates[i]);
            backtracing(candidates, target, i + 1, used);   // 由于每个位置的值只能取一次, 所以递归时startIndex的参数需要是i+1
            sum -= candidates[i];
            used[i] = false;
            current.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);        // 初始化一个用于标记某个位置的元素是否被取出的布尔型数组
        sort(candidates.begin(), candidates.end());         // 通过排序将一样的值排列在一起
        backtracing(candidates, target, 0, used);
        return this -> result;
    }
};

131.分割回文串

代码随想录链接

题目

LeetCode-131.分割回文串

给定一个字符串, 要求返回所有分割方式, 每种分割方式内的分割出的子串都是回文.

自己的想法

刚开始懵了. 真的不知道咋写.但是毕竟知道是要拿回溯法写

分割字符串和上面的取组合其实是类似的. for循环横向遍历的是当前字符串不断从startIndex开始向右延长, 纵向递归的是对剩下的字符串进行分割.

在分割的过程中如果一种分割方法产生的子串不是回文, 则应该立即结束这种分割方式, 不应进行纵向递归.

题解

class Solution {
private:
    vector<vector<string>> result;
    vector<string> current;
    void backtracing(const string &s, int startIndex) {
        if (startIndex >= s.size()) {   // 如果递归到了startIndex大于等于字符串长度的位置, 说明current内目前存的都是回文子串, 应该保存当前结果
            result.push_back(current);
            return;
        }

        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                current.push_back(s.substr(startIndex, i - startIndex + 1));    // 当前以startIndex开头, 以i结尾的字符串是回文时, 才应该推入current,并进行纵向递归
            } else continue;
            backtracing(s, i + 1);  // 递归分割下一个当前子串之后一个字符开始的字符串
            current.pop_back();
        }
    }

    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;
    }
public:
    vector<vector<string>> partition(string s) {
        backtracing(s, 0);
        return result;
    }
};