算法随想Day24【回溯算法】| LC39-组合总和、LC40-组合总和Ⅱ、LC131-分割回文串

LC39. 组合总和

vector<int> temp;
int sum = 0;
void combinationSumLoop(vector<vector<int>>& result, vector<int>& candidates, int index, const int& target)
{
    if (sum > target)
    {
        return;
    }
    if (sum == target)
    {
        result.emplace_back(temp);
        return;
    }
    for (int i = index; i < candidates.size(); i++)
    {
        temp.emplace_back(candidates[i]);
        sum += candidates[i];
        combinationSumLoop(result, candidates, i, target);
        temp.pop_back();
        sum -= candidates[i];
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
    vector<vector<int>> result;
    combinationSumLoop(result, candidates, 0, target);
    return result;
}

LC40. 组合总和Ⅱ

注释中，开始时这样的判断是不合理的，改进的是，要考虑到两种情况：

• 如例子1, 1, 2, 2, 2, 5 ，target = 5，不去重的话，会出现很多[1, 2, 2]的重复组合
• 有可能是第一个“1”递归完了，往右访问到第二个“1”的时候，重复了
• 也可能是在第一个“1”递归中，把前两个“2”放入temp后，往右访问到下一个“2”时，重复了

所以为了同时顾及上述两种情况，用一个变量prev_pop去保存上一次回溯时pop出来的值，下次往前访问时，对比是否与该值一致，是则跳过这次递归。

vector<int> temp;
int sum = 0;
int prev_pop = 0;
void combinationLoop(vector<vector<int>>& result, vector<int>& candidates, int index, const int& target)
{
    if (sum > target)
    {
        return;
    }
    if (sum == target)
    {
        result.emplace_back(temp);
        return;
    }
    for (int i = index; i < candidates.size(); i++)
    {
        // if ((i != 0 && candidates[i] == candidates[i - 1] && temp.size() == 0) ||
        //     (temp.size() != 0 && candidates[i] == temp.back()))
        // {
        //     continue;
        // }
        if (candidates[i] == prev_pop)
        {
            continue;
        }
        temp.emplace_back(candidates[i]);
        sum += candidates[i];
        combinationLoop(result, candidates, i + 1, target);
        prev_pop = temp.back();
        temp.pop_back();
        sum -= candidates[i];
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
    vector<vector<int>> result;
    sort(candidates.begin(), candidates.end());
    combinationLoop(result, candidates, 0, target);
    return result;
}

LC131. 分割回文串

开始没想到分割字符串的思想，看了讲解，自己写一遍代码。

本题要注意的细节比较多，在终止条件的确定上卡顿了一些时间：

• 开始partitionLoop函数中的string& s，是使用string s的，每层递归有自己的s空间，但后面发现这样会很难做递归的整体管理，而且不好设定判断终止条件，开始定义了一个index参数，比较index == 源s.size()时return，但这道题不能保证每个字符串的递归深度，所以还是采用了string& s统一对源s字符串进行存储，同时对递归函数传s的索引下标(left、right)进行管理。
• 终止条件，当left == right时，已经作废了，这时也不会进入for循环了
• 开始对if (isPalindrome(str) == true)的判断，没有做else处理。没有考虑的情况，如例子，源s = "abaa"，若没有else处理，第一个a放入了temp中，判断"ba"不是回文串，但由于没做退出处理，在下一轮递归中，判断最后一个"a"是回文串，从而导致这次的temp结果记录的是["a", "a"]，出现了非预期结果。

vector<string> temp;
bool isPalindrome(string str)
{
    bool flag = true;
    int left = 0;
    int right = str.size() - 1;
    while (left < right)
    {
        if (str[left++] != str[right--])
        {
            flag = false;
        }
    }
    return flag;
}
void partitionLoop(vector<vector<string>>& result, string& s, int left, int right)
{
    if (left >= right)
    {
        result.emplace_back(temp);
        return;
    }
    for (int i = left; i < right; i++)
    {
        string str(s.begin() + left, s.begin() + i + 1);
        if (isPalindrome(str) == true)
        {
            temp.emplace_back(str);
        }
        else
        {
            continue;
        }
        partitionLoop(result, s, i + 1, right);
        temp.pop_back();
    }
}
vector<vector<string>> partition(string s)
{
    int size = s.size();
    vector<vector<string>> result;
    partitionLoop(result, s, 0, size);
    return result;
}