We will be using recursion for solving this problem. The idea is to navigate through each substring starting from first character and to check if it is a palindrome. If it is, then add the substring to solution list and do recur for remaining part. Below is code for solution in JAVA.
Example :
Input - "askgifiga"
Output - [[a, s, k, g, i, f, i, g, a], [a, s, k, g, ifi, g, a], [a, s, k, gifig, a]]
import java.util.Stack;
public class PallindromicPartition2 {
static Stack<String> currList;
static Stack<Stack> fullList;
private static Boolean isPallindrom(String str,int start,int end) {
while(start<=end) {
if(str.charAt(start)!=str.charAt(end))
return false;
start++;
end--;
}
return true;
}
private static void FindSubPalPartition(Stack<Stack> fullList, Stack<String> currList, int start, int end, String str) {
if(start>=end) {
Stack<String> currListClone = (Stack<String>) currList.clone();
fullList.push(currListClone);
return;
}
for(int i=start;i<end;i++) {
if(isPallindrom(str,start,i)) {
currList.push(str.substring(start, i+1));
FindSubPalPartition(fullList, currList, i+1, end, str);
currList.pop();
}
}
}
private static void FindAllPalPartition(String str) {
int len = str.length();
currList = new Stack<String>();
fullList = new Stack<Stack>();
FindSubPalPartition(fullList, currList, 0, len, str);
System.out.println(fullList);
}
public static void main(String[] args) {
String str = "askgifiga";
FindAllPalPartition(str);
}
}



