All Palindromic Partitions

1. You are given a string of length n.
2. You have to partition the given string in such a way that every partition is a palindrome.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A String of length n

Output Format

Check the sample ouput and question video.

Question Video Constraints

1 <= length of string <= 15

Sample Input

pep

Sample Output

(p) (e) (p) 
(pep) 

• Editorial

  This question is very similar to k - partitions. We will add an additional condition in the base case and check whether the sum of all the partitions is equal. If it is, we will print the answer.

  We will solve this by recursion and backtracking. We will place the elements of array at level.

  We will have two options - whether to form a new group with the current element or to place the current element in any already present group. If there are many empty groups, we will place the element only in one (to avoid permutation). Some of the base cases -

  1.  k == 1 - If k is equal to one, we will print the array as one set is the whole array.
  2. If k > n - We will print -1 as n cannot be divided into more than n subsets.
  3. If sum of arrays is not divisible by k - print -1, as after each partition, we divide array into k subsets and their sum is equal therefore let the sum of each subset is x / k.

  Signature -

  public static void solution(int[] arr, int vidx, int n , int k, int[] subsetSum, int ssssf,    ArrayList> ans)

  arr- input array.

  vidx - current index

  n - size of the input array

  k - number of subsets.

  subsetSum - an auxiliary array of size k that stores the sum of the kth set.

  ssssf - number of non-empty sets till level n.

  ans- ArrayList of size k that stores the answer till that level.

  Code  -

  public static void solution(int[] arr, int vidx,int n , int k,int[] subsetSum,int ssssf, ArrayList
  > ans) {
                                      if(vidx == arr.length) {
                                  	if(ssssf == k) {
                                      	   int isum = subsetSum[0];
                                    	   boolean flag = true;
                                  	   for(int i = 1  ;i  < subsetSum.length; i++) {
                                  		if(subsetSum[i] == isum) {
                                  		   continue;
                                  		}else {
                                  		   flag = false;
                                  		   break;
                                  	  	}
                                  	   }
                                  	   if(flag == true) {
                                  		for(ArrayList
   a : ans) {
                                  			System.out.print(a + " ");
                                  		}
                                  		System.out.println();
                                  	   }
                                  	}
                                  	return;
                                      }
                                  		
                                      for(int j = 0 ; j < ans.size(); j++) {
                                  	if(ans.get(j).size() == 0) {
                                  	   ans.get(j).add(arr[vidx]);
                                  	   subsetSum[j] += arr[vidx];
                                  	   solution(arr,vidx + 1,n,k,subsetSum,ssssf + 1,ans);
                                  	   ans.get(j).remove(ans.get(j).size() - 1);
                                  	   subsetSum[j] -= arr[vidx];
                                  	   break;
                                  	} else {
                                  	   ans.get(j).add(arr[vidx]);
                                  	   subsetSum[j] += arr[vidx];
                                  	   solution(arr,vidx + 1,n,k,subsetSum,ssssf,ans);
                                  	   ans.get(j).remove(ans.get(j).size() - 1);
                                  	   subsetSum[j] -= arr[vidx];
                                  	}
                                      }
                                  }

  java false

  Code explained -

  Initially vidx is equal to zero, subsetSum is an array of size k with zero values, ssssf is zero and ans is an empty arraylist of size k.

  We have to consider two cases at every level -

  Case 1 - to make a new set.

  Case 2 - to add the current element to any of the already present set.

  We use a FOR loop at every level. If the size of the ArrayList for the jth set is zero - it means that jth set is empty, then we add the arr[vidx] to that set (make a new set) and break out of the loop as size of all the set after that will be zero and to avoid permutations, we break(Case 1). We also add the arr[vidx] to the jth index of subsetSum as we are adding an element in that set, we increase its sum in pre - order and decrease it in post - order. As the number of sets is increased in this case, therefore, we will increase ssssf in this case. If the size of the jth set is not zero, we add arr[vidx] to that set (Case2). As the number of sets remains constant, we would not increase ssssf. Here also we will increase the jth index of subsetSum by arr[vidx] in pre - order and decrease it in post order.

  In pre-order we add the arr[vidx] to the jth set and in post-order we remove it.

  Base Case -

  If vidx is equal to n, this means we have used all the elements of the array. If ssssf is be equal to k, we will check if the sum of all the set is equal. If it is, we will print the answer. We will return from the base case.

  Recursion Tree -

• Asked in Companies
• Related Topics