class Solution {
public:
vector<vector<string>>res;
 vector<vector<string>> partition(string s)
 {
     dfs(s,{});
     return res;
 }

 void dfs(string s,vector<string>ans)
 {
     if(s.length()==0)
     {
         res.push_back(ans);
     }
     for(int i=1;i<=s.length();i++)
     {
         string str=s.substr(0,i);
         if(f(str))
         {
             ans.push_back(str);
             dfs(s.substr(i),ans);//回溯，如果(0,i)个字符所组成的字符串为回文串那么从第i个字符往后找
             ans.pop_back();
         }
     }
 }

bool f(string s)//判断是否为回文串
{
    int left=0,right=s.length()-1;
    while(left<=right)
    {
        if(s[left]!=s[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
};