算法刷题Day27 | 39. 组合总和、40.组合总和II、131.分割回文串

0 引言

趁着周末赶紧追

1 组合总和

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

1.1 我的解题

这道题其实就是可以把已经遍历的元素再遍历一次，就是改变了 firstIndex 的位置而已。逻辑和之前的题目类似。还有终止条件不太一样就是。

class Solution
{
public:
    // 1. 回溯函数参数和返回值
    void backTracing(vector<int>& candidates, int target, int firstIndex, vector<int>& path, vector<vector<int>>& paths)
    {
        // 2. 终止条件
        int sum = 0;
        for (auto data : path)
        {
            sum += data;
        }
        if (sum > target)
        {
            return;
        }
        if (sum == target)
        {
            paths.emplace_back(path);
            return;
        }

        // 3. 单层回溯逻辑
        for (int i = firstIndex; i < candidates.size(); i++)
        {
            path.emplace_back(candidates[i]);
            backTracing(candidates, target, i, path, paths);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        vector<vector<int>> paths;
        vector<int> path;
        backTracing(candidates, target, 0, path, paths);
        return paths;
    }

};

2 组合总和II

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

2.1 解题

这道题注意了，集合中不能有重复的。上一道题简单的改变 firstIndex 就可以避免重复的组合是因为，给出的集合中本身不含有重复的数字。但是这道题中是包含重复数字的。

这道题比较难，理解关键点在于去重：树层去重、树枝去重。

那么如何判断当前是同一层还是树枝呢？使用一个额外的 used 数组来标识。

详细的解释参考文档。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};

3 分割回文串

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

3.1 切割

使用回溯进行切割是如何进行的呢？如何切割是回溯的一种经典题目了。

犀利糊涂写出来了，有一个疑惑的地方，在判断当前子串不是回文串时，为什么是进入下一个循环而不是跳出所有循环。

因为同一个循环内是同一层，加入当前层的前面有一个节点不满足，直接break的话，后面满足的节点也会被去除。所以应该使用continue。continue是跳过当前的节点，也就是说以这个节点为根的所有结果肯定都是不满足的。

class Solution {
public:
    // 判断是否是回文串
    bool isPalindrome(string s)
    {
        for (int i = 0; i < s.size()/2; i++)
        {
            if (s[i] != s[s.size() - 1 - i])
            {
                return false;
            }
        }
        return true;
    }

    // 回溯 (startIndex从0开始)
    void backTracing(string& s, int startIndex, vector<string>& path, vector<vector<string>>& paths)
    {
        // 终止条件
        if (startIndex == s.size())
        {
            paths.emplace_back(path);
            return;
        }

        // 单层回溯逻辑
        for (int i = startIndex; i < s.size(); i++)
        {
            string tmp = s.substr(startIndex, i - startIndex + 1);
            if (isPalindrome(tmp))
            {
                path.emplace_back(tmp);
                backTracing(s, i + 1, path, paths);
                path.pop_back();
            }
            else
            {
                continue;	// 注意是continue ，而不是break
            }
        }
    }

    vector<vector<string>> partition(string s) 
    {
        vector<string> path;
        vector<vector<string>> paths;
        backTracing(s, 0, path, paths);
        return paths;
    }
};