It can be solved using DP in O(2^N) time and O(N*N) space


#1

Hint: You just need to store if A[i…j] is a palindrome or not somehow.


#2

bool Ispalindrome(string s) {
string r(s);
reverse(s.begin(), s.end());
if (r.compare(s) == 0)return true;
else return false;
}

vectorhelper;

//_______________________________________________________________________________
void Partition(string input, int n, int be, vector<vector >&ans) {
if(input.size()<=0)return;

if (be == n) {

    ans.push_back(helper);

return ;
}
if (be > n)return;

//k is number of element for partion possibel
for (int k = 1; k <=input.size()-be; k++) {

    string sub = input.substr(be, k);
    bool check = Ispalindrome(sub);
    if (check == true) {
        helper.push_back(sub);
        
        Partition(input, n, be + k , ans);
        helper.pop_back();
    }

}

}
//___________________________________________________________________________________
vector<vector > Solution::partition(string A) {
vector<vector >answer;
int n =A.size();

Partition(A, n, 0, answer);
return answer;

}