All Palindromic Partitions
1. You are given a string of length n.Input Format
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.
A String of length nOutput Format
Check the sample ouput and question video.Question Video
1 <= length of string <= 15Sample Input
pepSample 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 
 k == 1  If k is equal to one, we will print the array as one set is the whole array.
 If k > n  We will print 1 as n cannot be divided into more than n subsets.
 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 nonempty 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 preorder we add the arr[vidx] to the jth set and in postorder 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