Description

Submission

class Solution {
    int dp[20][20];
    vector<vector<string>> rets;

    void backtrack(int i, string& s, vector<string> tmp) {
        cout << i << " ";
        if(i == s.size()) {
            rets.push_back(tmp);
        }
        for(int j = i; j < s.size(); ++j) {
            if(dp[i][j]) {
                tmp.push_back(s.substr(i, j-i+1));
                backtrack(j+1, s, tmp);
                tmp.erase(tmp.end()-1);
            }   
        }
    }
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // length = 1
        for(int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        // length = 2
        for(int i = 1; i < n; ++i) {
            if(s[i] == s[i-1]) dp[i-1][i] = 1;
        }
        // length >= 2

        for(int len = 3; 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];
            }
        }

        vector<string> tmp;
        backtrack(0, s, tmp);

        return rets;
    }
};