Print all Palindromic Partitions

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>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * 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);
	}
}