回溯法-分割问题的模板题。只要记住每次加入一段回文串即可，记得先预处理，快速判断f[i,j]是不是回文串

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path; // path中加入的都是回文串
    vector<vector<bool>> f;

    vector<vector<string>> partition(string s) {
        int n = s.size();
        f = vector<vector<bool>> (n, vector<bool>(n, false));
        // 预处理：快速判断f[i,j]这一段是否是回文串
        for (int j = 0; j < n; j ++) { // 必须先枚举j，这样f[i + 1][j - 1]才是先算好的
            for (int i = 0; i <= j; i ++) {
                if (s[i] == s[j]) {
                    // 前两个斜线由j - i <= 1来处理
                    if (j - i <= 1 || f[i + 1][j - 1] == true) f[i][j] = true;
                }
            }
        }

        dfs(s, 0);
        return res;
    }

    // 回溯法：我每次加进来一段回文串（分割问题）
    void dfs(string s, int u) {
        // 出口
        if (u == s.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < s.size(); i ++) {
            if (f[u][i] == true) { // 找一段回文串加入，而组合问题是每次加入一个数
                path.push_back(s.substr(u, i - u + 1));
                dfs(s, i + 1); 
                path.pop_back();
            }
        }
    }

};