Hey Guys I was checking out a book on algorithms I came across this problem (Author S.Dasgupta et al).
Here is the Question :
Sorry for the pic above didn't wanna paste text as the summation symbol was coming as crap.So the program below doesn't use dynamic programming. But it gets the job done :) it is not neat and needs a lot of refinement too :(. But u get the core idea here.
Filename PartionThree.java
/*---------------------------------------BEGIN----------------------------------------------------*/
public class PartitionThree {
public static void main(String args[]){
//int[] arr = { 1, 2, 3, 4, 4, 5, 8};
//int[] arr = {3,3,2,4,5,1};
int[] arr = {2,2,3,5};
int sum = arrSum(arr,arr.length);
int[] arr1 = new int[arr.length];
int[] arr2 = new int[arr.length];
int[] arr3 = new int[arr.length];
boolean ret = findPartition(sum/3, arr.length, arr, arr1,0, arr2,0, arr3,0);
if(ret == false)
System.out.println("Not Found Finally");
}
static boolean findPartition(
int sum,
int n,
int[] arr,
int[] arr1,int n1,
int[] arr2,int n2,
int[] arr3,int n3) {
if(found == true) {
return false;
}
int s1 = arrSum(arr1,n1);
int s2 = arrSum(arr2,n2);
int s3 = arrSum(arr3,n3);
if(n<0) {
return false;
} else if((s1>sum) || (s2>sum) ||(s3>sum)){
return false;
} else if((sum == s1)&& (sum == s2)&&(sum == s3)) {
if(n==0 && arr1.length > 0 && arr2.length > 0 && arr3.length > 0) {
System.out.print("Found ");
printArr(arr1,n1);printArr(arr2,n2);printArr(arr3,n3);
found = true;
return true;
} else {
return false;
}
} else if(n==0) {
return false;
} else {
arr1[n1] = arr[n-1];
boolean ret1 = findPartition(sum,n-1,arr,arr1,n1+1,arr2,n2,arr3,n3);
arr2[n2] = arr[n-1];
boolean ret2 = findPartition(sum,n-1,arr,arr1,n1,arr2,n2+1,arr3,n3);
arr3[n3] = arr[n-1];
boolean ret3 = findPartition(sum,n-1,arr,arr1,n1,arr2,n2,arr3,n3+1);
return (ret1||ret2||ret3);
}
}
static int arrSum(int arr[],int n) {
int sum =0;
for(int i=0;i < n;i++) {
sum += arr[i];
}
return sum;
}
static void printArr(int[] arr,int n) {
System.out.print("[");
for(int i=0;i < n;i++) {
System.out.print(arr[i] + " ");
}
System.out.print("] ");
}
static boolean found = false;
}
/*---------------------------------------END----------------------------------------------------*/
I will solve this using dynamic programming soon. Also please note that we can extend the above algorithm to handle n-partition. It is a highly inefficient algorithm turns out to be a (No. of partition) ^ N complexity.
Would love to here from you.
I miss hanging out in sankey tank.
