39. 组合总和

同一个下标可以被多次选择，dfs 的 for 循环下标从当前开始。

class Solution {
public:
    // 多个
    // ==0加入 <0终止 >0继续  
    // dfs的循环很妙
    vector<int> candidates;
    vector<vector<int>> res;
    vector<vector<int>> combinationSum(vector<int>& candidates_, int target) {
        candidates = candidates_;
        vector<int> path;
        for (int i = 0; i < candidates.size(); i ++)
        {
            path.push_back(candidates[i]);
            dfs(path, i, target - candidates[i]);
            path.pop_back();
        }
        return res;
    }

    // 路径 下标 当前总和
    void dfs(vector<int>& path, int u, int sum)
    {
        if (sum < 0)
        {
            return; // 剪枝
        }
        if (sum == 0)
        {
            res.push_back(path);
            return;
        }

        // 下一层任然要从begin下标开始
        for (int i = u; i < candidates.size(); i ++)
        {
            path.push_back(candidates[i]);
            dfs(path, i, sum - candidates[i]);
            path.pop_back();
        }
    }
};

40. 组合总和 II

每个下标只能选择一次。往下递归时不去重，同一层要去重。

实现这个逻辑的核心是 if (i > u + 1 && candidates[i] == candidates[i-1]) continue;

class Solution {
public:
    // 如何处理只能使用一次?
    vector<vector<int>> res;
    vector<int> candidates;
    vector<vector<int>> combinationSum2(vector<int>& candidates_, int target) {
        candidates = candidates_;
        sort(candidates.begin(), candidates.end());
        vector<int> tmp;
        tmp.push_back(candidates[0]);
        dfs(tmp, 0, target - candidates[0]);
        for (int i = 1; i < candidates.size(); i ++)
        {
            if (candidates[i] == candidates[i-1])
                continue;
            tmp = {};
            tmp.push_back(candidates[i]);
            dfs(tmp, i, target - candidates[i]); //前面会清空
        }
        return res;
    }

    //tmp数组 下标u 当前总和sum
    void dfs(vector<int>& tmp, int u, int sum)
    {
        if (sum < 0) return;
        if (sum == 0)
        {
            res.push_back(tmp);
            return;
        }

        for (int i = u + 1; i < candidates.size(); i ++)
        {
            if (i > u + 1 && candidates[i] == candidates[i-1]) continue;  // 同一行去重
            tmp.push_back(candidates[i]);
            dfs(tmp, i, sum - candidates[i]);
            tmp.pop_back();
        }
    }
};

131. 分割回文串

待处理字符串最多选择一个子串加到vector里面。

循环结尾的点，爆搜。

class Solution {
public:
    // 每一个点作为起点, 把所有的可能弄出来
    vector<vector<string>> res;
    string s;
    vector<vector<string>> partition(string s) {
        this->s = s;
        vector<string> vec;
        string s0;
        s0 += s[0];
        vec.push_back(s0);
        dfs(vec, 1);
        for (int i = 1; i < s.size(); i ++)
        {
            vec = {};
            string t = s.substr(0, i + 1);
            if (!ishuiwen(t)) continue;
            vec.push_back(t);
            dfs(vec, i + 1);
        }
        return res;
    }

    // vec是数组 u下标
    void dfs(vector<string>& vec, int u)
    {
        if (u == s.size())
        {
            res.push_back(vec);
            return;
        }
        // u是起点
        for (int i = u; i < s.size(); i ++)
        {
            string t = s.substr(u, i - u + 1);
            if (!ishuiwen(t)) continue;
            vec.push_back(t);
            dfs(vec, i + 1);
            vec.pop_back();
        }
    }

    bool ishuiwen(string s)
    {
        int L = 0, R = s.size() - 1;
        while (L < R)
        {
            if (s[L] != s[R]) return false;
            L ++, R --;
        }
        return true;
    }
};