问题

输出所有字符串分割方案，使得所有子串都是回文串

算法: DFS+剪枝

这道题的思路很简单：直接暴搜，枚举所有“放板子”的方案。难点在于确定一个不重不漏的搜索顺序。

关键问题是，怎么表示放/不放板子？如果不放板子，就是在当前字符串上累加字符；如果放板子，就是记录下当前字符串，同时在当前位置开启一个新的字符串。

如何剪枝？关键问题是：需要每个地方都放板子嘛？并不是。那什么时候需要放板子？自然是已经找到一个回文串的时候。如果没有找到回文串，则继续向当前串添加字符（剪枝）。当然，如果找到一个回文串，我们不仅需要检查放板子的方案，也需要检查不放板子的方案。

时间复杂度

$O(2^N·N)$, 放板子与不放板子为2^N，检查回文串为N

代码

class Solution {
public:
    vector<string> path;
    vector<vector<string>> ans;
    vector<vector<string>> partition(string s) {
        dfs("", 0, s);
        return ans;
    }
    bool check(string s){
        if(s.empty()) return false;
        for(int i = 0, j = s.size()-1; i < j; i ++, j --){
            if(s[i] != s[j]) return false;

        }
        return true;
    }
    void dfs(string now, int u, string& s){
        if(u == s.size()){
            if(check(now)){
                path.push_back(now);
                ans.push_back(path);
                path.pop_back();
            }
            return;
        }
        if(check(now)){
            path.push_back(now);
            dfs("", u, s); // 当前区间是回文串，因此可以将其分割
            path.pop_back();
        }
        dfs(now+s[u], u+1, s); // 不管当前区间是否为回文串都需要检查一下不分隔的情况

    }
};