<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 pali(string s){
        bool check = true ;
        for(int i = 0 ; i < s.length() / 2 ; i++){
            if(s[i] != s[s.length() - 1 - i]){
                return false ;
            }
        }
        return true ;
    }
    
    void solve(string &s , int i , string c , vector<vector<string>> &answer , vector<string> &st){
       if(i == s.length()){
        bool check = true ;
        for(auto i : st){
            check = check && pali(i);
        }
        if(check == true){
            answer.push_back(st);
        }
        return ;
       }
       c.push_back(s[i]);
       st.push_back(c);
       solve(s , i+1 , "" , answer , st);
       st.pop_back();
       solve(s , i + 1 , c , answer , st);
    }
     vector<vector<string>> answer1 ;

    vector<vector<string>> partition(string s) {
        vector<vector<string>> answer ;
        vector<string> st ;
        solve(s , 0 , "" , answer , st);
        for(int i = 0 ; i < answer.size() ; i++){
            int count = 0 ;
            for(int j = 0 ; j < answer[i].size() ; j++){
                for(int k = 0 ; k < answer[i][j].length() ; k++){
                    count++;
                }
            }
           
            if(count == s.length()){
                answer1.push_back(answer[i]);
            }
        }
        return answer1 ;
    }
};
164811