<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:
    bool isPalindrome(string s){
        for(int i = 0; i < s.size(); i++) if(s[i] != s[s.size() - 1 - i]) return false;
        return true;
    }

    vector<vector<string>> pp(vector<vector<vector<string>>>& dp, vector<bool>& visited, string& s, int i){
        if(i >= s.size()) return {{}};
        else if(visited[i]) return dp[i];
        else{
            visited[i] = 1;
            string str = "";
            for(int j = i; j < s.size(); j++){
                str += s[j];
                if(isPalindrome(str)){
                    vector<vector<string>> next = pp(dp,visited,s,j+1);
                    for(int k = 0; k < next.size(); k++){
                        dp[i].push_back({str});
                        dp[i].back().insert(dp[i].back().end(),next[k].begin(),next[k].end());
                    }
                }
            }
            return dp[i];
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<vector<string>>> dp(s.size());
        vector<bool> visited(s.size(),0);
        return pp(dp,visited,s,0);
    }
};
158439