Given a string, print all possible palindromic partitions

Given a string, find all possible palindromic partitions of given string.

Example:

We strongly recommend you to minimize your browser and try this yourself first.

Note that this problem is different from Palindrome Partitioning Problem, there the task was to find the partitioning with minimum cuts in input string. Here we need to print all possible partitions.

The idea is to go through every substring starting from first character, check if it is palindrome. If yes, then add the substring to solution and recur for remaining part. Below is complete algorithm.

Below is C++ implementation of above idea

// C++ program to print all palindromic partitions of a given string #include<bits/stdc++.h> using namespace std;   // A utility function to check if str is palindroem bool isPalindrome(string str, int low, int high) {     while (low < high)     {         if (str[low] != str[high])             return false;         low++;         high--;     }     return true; }   // Recursive function to find all palindromic partitions of str[start..n-1] // allPart --> A vector of vector of strings. Every vector inside it stores //           a partition // currPart --> A vector of strings to store current partition void allPalPartUtil(vector<vector<string> >&allPart, vector<string> &currPart,                    int start, int n, string str) {     // If 'start' has reached len     if (start >= n)     {         allPart.push_back(currPart);         return;     }       // Pick all possible ending points for substrings     for (int i=start; i<n; i++)     {         // If substring str[start..i] is palindrome         if (isPalindrome(str, start, i))         {             // Add the substring to result             currPart.push_back(str.substr(start, i-start+1));               // Recur for remaining remaining substring             allPalPartUtil(allPart, currPart, i+1, n, str);                           // Remove substring str[start..i] from current             // partition             currPart.pop_back();         }     } }   // Function to print all possible palindromic partitions of // str. It mainly creates vectors and calls allPalPartUtil() void allPalPartitions(string str) {     int n = str.length();       // To Store all palindromic partitions     vector<vector<string> > allPart;       // To store current palindromic partition     vector<string> currPart;       // Call recursive function to generate all partiions     // and store in allPart     allPalPartUtil(allPart, currPart, 0, n, str);       // Print all partitions generated by above call     for (int i=0; i< allPart.size(); i++ )     {         for (int j=0; j<allPart[i].size(); j++)             cout << allPart[i][j] << " ";         cout << "\n";     } }   // Driver program int main() {     string str = "nitin";     allPalPartitions(str);     return 0; }

Output:

n i t i n
n iti n
nitin

This article is contributed by Ekta Goel. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.