public static boolean partition(int[] input){
        int totalSum = findSum(input);
        //if some is odd, there cannot be a partition
        if(totalSum%2==1) {
            return false;
        }

        int halfSum = totalSum/2;

        //sum array describes sum[a][b][c] where a - 0...index of item , b - length, c - sum
        boolean [][] sum = new boolean[halfSum+1][input.length];

        for( int i=0; i< input.length; i++){
            sum[0][i] = true;
        }


        for( int i=1; i< halfSum+1; i++) {
            for (int j =0; j< input.length; j++){

                sum[i][j] = j-1 >= 0? sum[i][j-1]: false;

                if(i == input[j]){
                    sum[i][j] = true;
                }
                if( i>input[j]){
                    sum[i][j] = sum[i][j] || j-1>=0?sum[i-input[j]][j-1]: false;

                }


            }
        }


        return sum[halfSum][input.length-1];
    }