代码随想录训练营Day19 | 39. 组合总和 - 40.组合总和II - 131.分割回文串

39. 组合总和

• 题目链接：39. 组合总和
• 思路：
  1. 和组合总数思路一样，唯一不一样的可以重复选择某一个数，所以回溯函数传递下表参数时不用+1，就可以重复选择
• 代码：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& c, int t) {
        vector<vector<int>> ans;
        vector<int> tmp;
        int n = c.size();
        ranges::sort(c); // 排序
        auto dfs = [&](auto&& dfs, int s, int k) {
            if(k == 0) {
                ans.push_back(tmp);
                return;
            }
            if(s == n || k < c[s]) // 退出条件 + 当k值比能选的最小值选的时候 减枝优化
                return;
            for(int i = s; i < n; ++i) {
                tmp.push_back(c[i]);
                dfs(dfs, i, k - c[i]);
                tmp.pop_back();
            }
        };
        dfs(dfs, 0, t);
        return ans;
    }
};

40.组合总和II

• 题目链接：40.组合总和II
• 思路：
  1. 和上题一模一样的思路，唯一的不用点，同一个数不能重复选择，回溯函数传递时下表需要+1
  2. 同一个 数字不能重复选择之外，还需要去除掉相同数字，让相同数字每次选择只能选择一次
• 代码：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& c, int t) {
        vector<vector<int>> ans;
        vector<int> tmp;
        int n = c.size();
        ranges::sort(c);
        auto dfs = [&](auto&& dfs, int s, int k) {
            if(k == 0) {
                ans.push_back(tmp);
                return;
            }
            if(s == n || k < c[s]) // 退出条件 + 当k值比能选的最小值选的时候 减枝优化
                return;
            for(int i = s; i < n; ++i) {
                if(i != s && c[i] == c[i-1]) // 去掉重复数字，每一次相同数字只能选择一次
                    continue;
                tmp.push_back(c[i]);
                dfs(dfs, i+1, k - c[i]);
                tmp.pop_back();
            }
        };
        dfs(dfs, 0, t);
        return ans;
    }
};

131.分割回文串

• 题目链接：131.分割回文串
• 思路：思路同组合是一致的，只不过这里的条件是，每次选择都要保证选择的字符串是回文串，需要写一个回文字符串判断函数
• 代码：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> rs;
        vector<vector<string>> ans;
        int n = s.length();
        auto isPalinDromic = [&](string& ss) -> bool { // 判断回文字符串函数
            int i = 0;
            int j = ss.length() - 1;
            while(i < j) {
                if(ss[i++] != ss[j--])
                    return false;
            }
            return true;
        };

        auto dfs = [&](auto&& dfs, int i) {
            if(i == n) {
                ans.push_back(rs); // 符合结果
                return;
            }

            string tmp = "";
            for(int j = i; j < n; ++j) {
                tmp += s[j]; // 添加字符
                if(isPalinDromic(tmp)) { // 判断是否是回文字符串
                    rs.push_back(tmp);
                    dfs(dfs, j + 1);
                    rs.pop_back();
                }
                 
            }
        };

        dfs(dfs, 0);
        return ans;
    }
};