131. 分割回文串

class Solution {
public:
    bool check(string s)
    {
        int n=s.size();
        for(int i=0;i<n/2;i++)
            if(s[i]!=s[n-i-1])
                return false;
        return true;
    }
    vector<vector<string>> res;
    vector<string> path;
    void dfs(string s,int u)
    {
        if(u==s.size())
        {
            res.push_back(path);
            return;
        }
        for(int i=u;i<s.size();i++)//枚举从当前字符到结尾可以选择的长度
        {
            if(!check(s.substr(u,i-u+1)))   continue;
            path.push_back(s.substr(u,i-u+1));
            dfs(s,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return res;
    }
};