<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string"><strong>palindrome</strong></span>. Return <em>all possible palindrome partitioning of </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> [["a","a","b"],["aa","b"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "a"
<strong>Output:</strong> [["a"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution {
public:
    int N;
    bool dp[16][16];
    vector<vector<string>> st;
    vector<vector<string>> partition(string s) {
        N = s.size();
        for(int i = 0; i < N; ++i) {
            dp[i][i] = 1;
        }
        for(int i = N-2; i >= 0; --i) {
            for(int j = i+1; j < N; ++j) {
                if(s[i] == s[j]) {
                    if((i+1 >= j-1) || dp[i+1][j-1]) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 0;
                    }
                }
            }
        }
        for(int i = 1; i < (1 << N); ++i) {
            if((i & (1 << (N-1))) == 0) continue;
            vector<int> v;
            for(int j = 0; j < N; ++j) {
                if(i & (1 << j)) v.push_back(j);
            }
            int l = 0;
            bool flag = true;
            for(int k = 0; k < v.size(); ++k) {
                int r = v[k];
                if(!dp[l][r]) flag = false;
                l = r+1;
            }
            if(flag) {
                vector<string> partition;
                int l = 0;
                for(int k = 0; k < v.size(); ++k) {
                    int r = v[k];
                    partition.emplace_back(s.substr(l, r-l+1));
                    l = r+1;
                }
                st.push_back(partition);
            }
        }
        return st;
    }
};
161625