<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.length()/2; i++)
            if(s[i]!=s[s.length()-1-i])
                return false;
        return true;
    }

    set<vector<string>> partition_reverse(string s) 
    {
        if(s.length()==1)
            return {{s}};
        string firstchar = s.substr(0, 1);
        // cout << firstchar << "\n";
        string rest = s.substr(1, s.length()-1);
        // cout << rest << "\n";
        auto parts = partition_reverse(rest);
        set<vector<string>> ans;
        for(auto vec : parts){
            vec.push_back(firstchar);
            ans.insert(vec);
        }

        // for(auto vec : ans)
        // {
        //     for(auto str : vec)
        //     {
        //         cout << str << " ";
        //     }
        //     cout << "\n";
        // }

        for(auto vec : parts)
        {
            string str = "";
            while(vec.size()>0)
            {
                str += vec.back();
                if(isPalindrome(firstchar+str))
                {
                    vec[vec.size()-1] = firstchar+str;
                    ans.insert(vec);
                }
                vec.pop_back();
            }
        }


        // for(auto vec : ans)
        // {
        //     for(auto str : vec)
        //     {
        //         cout << str << " ";
        //     }
        //     cout << "\n";
        // }

        return ans;
    }

    vector<vector<string>> partition(string s)
    {
        auto setans = partition_reverse(s);

        vector<vector<string>> ans;
        for(auto& vec : setans)
            ans.push_back(vec);

        for(auto& vec : ans)
            reverse(vec.begin(), vec.end());


        return ans;
    }
};
203046