class Solution {
public:
    vector<vector<string>> partition(string s) 
    {
        vector<vector<string>> result;
        vector<string> v;
        for(int i=0;i<s.length();i++) v.push_back(" ");
        generate(s,result,v,0,0);
        return result;
    }
    bool check(const string& s,int l,int r)
    {
        while(l<r && s[l]==s[r]) 
        {
            l++;
            r--;
        }
        if(l>=r)
            return true;
        else
            return false;
    }
    void generate(string& s,vector<vector<string>>& result,vector<string>& v,int sdep,int vdep)
    {
        if(sdep==s.length())
        {
            vector<string> vnew;
            for(int i=0;i<vdep;i++)
                vnew.push_back(v[i]);
            result.push_back(vnew);
            return;
        }
        string news="";
        for(int i=sdep;i<s.length();i++)
        {
            news=news+s[i];
            if(check(s,sdep,i))
            {
                v[vdep]=news;
                generate(s,result,v,i+1,vdep+1);
            }
        }
    }
};