算法思路

dfs + 回溯

dfs算法的过程其实就是一棵递归树，所有的dfs算法的步骤大概有以下几步：

• 找到中止条件，即递归树从根节点走到叶子节点时的返回条件，此时一般情况下已经遍历完了从根节点到叶子结点的一条路径，往往就是我们需要存下来的一种合法方案
• 如果还没有走到底，那么我们需要对当前层的所有可能选择方案进行枚举，加入路径中，然后走向下一层
• 在枚举过程中，有些情况下需要对不可能走到底的情况进行预判，如果已经知道这条路不可能到达我们想去的地方，那我们干嘛还要一条路走到黑呢，这就是我们常说的剪枝的过程
• 当完成往下层的递归后，我们需要将当前层的选择状态进行清零，它下去之前是什么样子，我们现在就要让它恢复原状，也叫恢复现场。该过程就是回溯，目的是回到最初选择路口的起点，好再试试其他的路。

将上述思路运用在该题中：
1. 从第一个字符开始枚举，用path数组存储一条从递归树根节点到叶子结点的合法方案，用res数组存下所有的合法方案
2. dfs过程的中止条件是当我们遍历完了所有字符，说明我们已经找到一条合法路径，此时将路径加入方案中
3. 然后进行该层的选择枚举，这里枚举从该字符到结尾的所有长度，且该长度的字符串为回文串时，我们将其加入路径中，然后递归到下一层
4. 当我们进行了下层的递归后，我们需要进行回溯，也就是恢复现场，目的是我们能够在该层重新做其他选择

C ++代码

class Solution {
public:
    vector<vector<string>> res; //所有方案
    vector<string> path; //一个合法方案
    vector<vector<string>> partition(string s) {
        dfs(0, s); //从位置0开始dfs
        return res;
    }

    void dfs(int u, string s)
    {
        if (u == s.size()) //遍历完整个字符串
        {
            res.push_back(path); //将路径加入方案
            return;
        }

        for (int i = u; i < s.size(); i ++) //枚举从当前字符到结尾可以选择的长度
        {
            if (check(s, u, i)) //判断u ~ i是否为回文串
            {
                path.push_back(s.substr(u, i - u + 1)); //加入路径
                dfs(i + 1, s); //递归下一层
                path.pop_back(); //回溯
            }
        }
    }

    bool check(string s, int l, int r) //判断从l到r是否为回文串
    {
        while (l <= r)
        {
            if (s[l ++] != s[r --])
                return false;
        }

        return true;
    }
};