Three Partition SubSet Sum Problem

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.