Finding all palindrome partitions in a string

The question is about finding all the palindrome partition in a string.

for eg: imagine we have a string "aab" then the answer will be [ [ " a" , "a", "b" ] , [ "aa" ,"b" ] ]

These are all the palindrome partition possible for the given string.

The problem is considered as a backtracking problem and recursion is our need.

Recursion simply means a function calling itself.

The approach is simple, we just have to start from the beginning index and check if it's a palindrome or not. If it is then we just have to add it to the answer and user recurrence for the remaining string.

The following code will show how to find the same.

Code

bool pal(string &str, int start, int end) // To check if the sub-string is palindrome or not
 {
 
 while(start<end)
 {
 if(str[start]!=str[end])
 return false;    // returning false if it is not palindrome
 start++;
 end--;
 }
 return true; // returning true if it is palindrome
}

void helper(int i,vector<string> &current, string &s, vector<vector<string> > &ans)
{
 if(s.length()==i){          // it means we have traversed the entire string so we need to 
 ans.push_back(current);          push the results into the answer
 return;
 }
 for(int j = i ; j <s.length();j++)
 {
 if(pal(str,i,j))         // calling function to check palindrome 
 {
 current.push_back(s.substr(i,j-i+1));    // adding particular palindrome string into current
 helper(j+1, current, s, ans);     // recursion for the remaining part of the string 
 current.pop_back();     // deleting string from the current to start from the next index
 }
 }
 
}
vector<vector<string> > partition(string s) 
{
 vector<vector<string> > ans;    // this will store the final result
 vector<string> current;           // this will store the current string 
 helper(0,current,s,ans);        // calling helper function
 return ans;                   // finally returning the answer
}