# Print all palindromic partitions of a string

## Given a string, write  a function to print all possible palindromic patitioning of s

### Example

INPUT
s = "bcc"

OUTPUT
[["b", "c", "c"],  ["b", "cc"]]

## Algorithm

1. Maintain two vectors, a 2D vector to store all the possible partitions and a temporory vector for storing the current partition

2. Increamentally check all substrings starting from index i for being palindromic. If found, recursively find for the remaining string and add this to our solution

## C++ Program

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

//checks whether the string is palindrome or not
bool isPalindrome(string str)
{
int n = str.length();
n--;
for (int i=0; i<n; i++)
{
if (str[i] != str[n])
return false;
n--;
}
return true;
}

void printPartitions(vector<vector<string> > partitions)
{
for (int i = 0; i < partitions.size(); ++i)
{
for(int j = 0; j < partitions[i].size(); ++j)
cout << partitions[i][j] << " ";
cout << endl;
}
return;
}

// Goes through all indexes and recursively add remaining
// partitions if current string is palindrome.
void addStrings(vector<vector<string> > &sol, string &s,
vector<string> &temp, int index)
{
int n = s.length();
string str;
vector<string> current = temp;
if (index == 0)
temp.clear();
for (int i = index; i < n; ++i)
{
str = str + s[i];
if (isPalindrome(str))
{
temp.push_back(str);
if (i+1 < n)
else
sol.push_back(temp);
temp = current;
}
}
return;
}

//stores all solutions in sol
void allPartitions(string s, vector<vector<string> >&sol)
{
vector<string> temp;
printPartitions(sol);
return;
}

int main()
{
string s = "bcc";
vector<vector<string> > partitions;
allPartitions(s, partitions);
return 0;
}``````

Scroll to Top