<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 {
    private:
     bool ispalindrome(string str,int s,int e){
    while(s<e){
        if(str[s]!=str[e]){return false;}
        s++;
        e--;
    }
    return true;
}

void fn(string &str, int n, vector<vector<string>>&ans,vector<pair<int,int>>temp,int s=0,int e =0){
    bool ispal  = false;
    if(e==n){ispal = ispalindrome(str,s,e-1);}
    else{ ispal = ispalindrome(str,s,e);}

    if(e==n-1 ){
        if(ispal){
            temp.push_back({s,e});
            vector<string>tmp;

        for(auto i:temp){
            string res ="";
            for(int j=i.first;j<=i.second;j++){   
                res+=str[j];
            }
            tmp.push_back(res);
        }
          ans.push_back(tmp);
        }
        return ;
    }
        fn(str,n,ans,temp,s,e+1);
    if(ispal){
        temp.push_back({s,e});        
        fn(str,n,ans,temp,e+1,e+1);
    }
}
public:
    vector<vector<string>> partition(string s) {
         int n = s.size();
    vector<pair<int,int>>temp;
    vector<vector<string>>ans;
    fn(s,n,ans,temp);
        return ans;
    }
};
298634