# Print all Palindromic Partitions

Given a string, print all palindromic partitions of the given string.
Palindromic partitioning of a string is dividing the string into parts such that each part is a palindrome.

If abcb is a string, then
a-b-c-b and a-bcb will be palindormic partitions of the string.

a-b-cb, ab-cb, ab-c-b etc are partitions but not palindromic partitions of the string abcb.
b-c-b is palindromic but not a partition of the string abcb.

Example:

Input:
IDeserve
Output:
I-D-e-s-e-r-v-e
I-D-ese-r-v-e

Input:
banana
Output:
b-a-n-a-n-a
b-a-n-ana
b-a-nan-a
b-ana-n-a
b-anana

Amazon

## Algorithm/Insights

The solution is recursive where we find the palindromic substring of the string, add it to the output and recursively traverse for the remaining part of the string to find other possible palindromic substrings and hence partitions.

Steps:
1. If begin == end, print the current output string.
2. Loop for i = begin to end,
if substring of input string from begin to i is a palindrome then add substring from begin to i to the output string and recursively call for rest of the substring from i+1 to end.

## Code Snippet

```
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* Given a string, print all palindromic partitions of the given string.
*
* @author Saurabh
*/
public class AllPalindromicPartitions {
public static boolean ispalin(String input, int begin, int end) {
while (begin < end) {
if (input.charAt(begin) != input.charAt(end))
return false;
begin++;
end--;
}
return true;
}

public static void printpart(String input, String output, int begin, int end) {
if (begin == end) {
System.out.println(output);
return;
}
int n = input.length();
String delimiter = "-";
for (int i = begin; i < end; i++) {
if (ispalin(input, begin, i)) {
if (i+1 == n) {
delimiter = "";
}
printpart(input, output + input.substring(begin, i+1) + delimiter, i + 1, end);
}
}
}

public static void main(String[] args) {
String input = "abcb";
String output = "";
int begin = 0;
int end = input.length();
printpart(input, output, begin, end);
}
}
```