class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n=s.size();
        vector<vector<int>>dp(n,vector<int>(n,0));
        for(int i=1;i<n;i++)dp[i][i]=dp[i][i-1]=1;
        dp[0][0]=1;
        for(int len=2;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j=i+len-1;
                if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];
                else dp[i][j]=0;
            }
        }
        vector<vector<string>>ans;
        vector<string>ans1;
        dfs(0,s,dp,ans,ans1);
        return ans;
    }
    void dfs(int i,string &s,vector<vector<int>>&dp,vector<vector<string>>&ans,vector<string>&ans1){
        if(i==s.size()){
            ans.push_back(ans1);
            return;
        }
        for(int j=i;j<s.size();j++){
            if(dp[i][j]){
                string tmp=s.substr(i,j-i+1);
                ans1.push_back(tmp);
                dfs(j+1,s,dp,ans,ans1);
                ans1.pop_back();
            }
        }
    }
};