Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

The solution for this problem can be done with the help of DFS.

The logic is to loop through the string one by one. Once we find a palindromic string for the string str(0, i) we store the current string in “sub_result”. Then we recursively call “dfs” function to find palindrome string for rest of the sub string: subStr(i+1, length).

When we reach end of the string, copy the value in “sub_str” into “result” string.

Solution in C++

/*
* File     : palindrome_partitioning.cpp
*/

#include<iostream>
#include<vector>
#include<string>
using namespace std;

// function to check if a string is a palindrome or not 
bool isPalindrome(const string& s, int start, int end) 
{
    while(start <= end) 
    {
        if(s[start++] != s[end--])
            return false;
    }
    return true;
}


// function to perfor DFS
// index    = Start index of the string
// given_string = Original string from input
// sub_result = To store intermediate result
// result     = To return the final result

void dfs(int index, string& given_string, vector<string>& sub_result, vector<vector<string> >& result) 
{
    if(index == given_string.size()) 
    {
        result.push_back(sub_result);
        return;
    }

    for(int i = index; i < given_string.size(); ++i) 
    {
        if(isPalindrome(given_string, index, i)) 
        {
            sub_result.push_back(given_string.substr(index, i - index + 1));

            dfs(i+1, given_string, sub_result, result);

            sub_result.pop_back();
        }
    }
}

vector<vector<string>> get_partition(string given_string) 
{
    vector<vector<string> > result;
    if(given_string.empty()) return result;
    
    vector<string> sub_result;

    dfs(0, given_string, sub_result, result);
    
    return result;
}
    
int main()
{
  string given_string = "aab";

  vector< vector<string>> result = get_partition(given_string);

  cout<<"The result is = "<<endl;

  for (int i = 0; i < result.size(); i++)
  {
    for (int j = 0; j < result[0].size(); j++)
    {
      cout<< result[i][j]<<" ";
    }
    cout<<endl;
  }

}

Output:

The result is =
a a b
aa b