# print all palindromic partitions

## Given a string, write a function that will print all palindromic partitions of a given string

### Example

INPUT
s = “bcdcb”

OUTPUT
[‘b’, ‘c’, ‘d’, ‘c’, ‘b’]
[‘b’, “cdc”, ‘b’]
[“bcdcb”]

In this method the main idea is to use vectors, create a 2 dimensional vector to store all the partitions and a 1 dimensional vector to store the current partition

## Algorithm

1. Traverse through every substring starting from first charcater

2. If the substring is a palindrome, then add it to the solution

3. recur for the remaining part

## C++ Program

```#include<bits/stdc++.h>
using namespace std;

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

//Recursive function,
//sol is a vector of vectors, each vector store a partition
//cPartition is a vector of strings to store current partition
void recAllPPartitions(vector<vector<string> >&sol, vector<string> &cPartition,
int start, int n, string s)
{
// If 'start' has reached len
if (start >= n)
{
sol.push_back(cPartition);
return;
}

// Pick all possible ending points for substrings
for (int i=start; i<n; i++)
{
// If substring s[start..i] is palindrome
if (isPalindrome(s, start, i))
{
// Add the substring to result
cPartition.push_back(s.substr(start, i-start+1));

// Recur for remaining remaining substring
recAllPPartitions(sol, cPartition, i+1, n, s);

// Remove substring s[start..i] from current
// partition
cPartition.pop_back();
}
}
}

// Function to print all possible palindromic partitions of
// s. It mainly creates vectors and calls allPalPartUtil()
void printAllPPartitions(string s)
{
int n = s.length();

// To Store all palindromic partitions
vector<vector<string> > sol;

// To store current palindromic partition
vector<string> cPartition;

// to generate all partitions
recAllPPartitions(sol, cPartition, 0, n, s);

// Print all partitions
for (int i=0; i< sol.size(); i++ )
{
cout<<"[ ";
for (int j=0; j<sol[i].size(); j++)
cout << sol[i][j] << " ";
cout<<"]";
cout <<endl;

}
}

// Driver program
int main()
{
string s = "bcdcb";
printAllPPartitions(s);
return 0;
}```

Translate »