How to solve a partition problem using recursion only

Question

I got a partition problem for which I need advice. I'm given a 1D array whose length is even. I need to write a boolean method to determine whether the array can be divided into 2 equally sized subarrays with equal sum, no loops are allowed.

For example, array #1 {-3,5,-12,14,-9,13} will return false, because -3 + 5 -12 + 14 = -9 + 13, however on the left side there are 4 elements and on the other side 2.

array #2 will return true: {-3,14,12,5,-9,13} : -3 + 5 + 14 = 12 - 9 + 13

Here's what I've done so far:

public static boolean canBeDividedEqually(int[] arr)
{
    if (arr.length %2 ==0){
        return canBeDividedEquallyHelper(arr, 0, 0, 0);
    }
    return false;
}

public static boolean canBeDividedEquallyHelper(int[] arr, int i, int sum1, int sum2)
{
    if (i == arr.length){
        return sum1 == sum2;}
    
    return canBeDividedEquallyHelper(arr, i+1, sum1 + arr[i], sum2) ||
           canBeDividedEquallyHelper(arr, i+1, sum1, sum2 + arr[i]);
}

For case #2, it will return true as expected, but for case #1 it will also return true. I need to add a condition that will disqualify an array of type case #1.

Answer 1

Here's a solution without using loops,

static int[] arrA, arrB;
    public static boolean equalSplit(int[] arr) {
        //Step 1
        if (arr.length % 2 == 0) {
            int sumA = 0, sumB = 0; // Two int variables to store the value of sum.

            // Initializing the two new arrays with equal length.
            arrA = new int[arr.length / 2]; 
            arrB = new int[arr.length / 2];

            // Copying the elements from the given array to the new arrays.
            arrA = createArray(arrA, 0, arr, 0);
            arrB = createArray(arrB, 0, arr, arr.length / 2);

            //Calculating and storing the sum in the variables.
            sumA = arraySum(arrA, arrA.length);
            sumB = arraySum(arrB, arrB.length);

            return sumA == sumB; // Checking the codition

        } else {
            return false;
        }
    }

    private static int[] createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) {
        if(index == arr.length) return arr;
        arr[index] = copyFrom[copyFromIndex];
        index++;
        copyFromIndex++;
        return createArray(arr, index, copyFrom, copyFromIndex);
    }

    private static int arraySum(int[] arr, int N) {
        if (N <= 0) return 0;
        return (arraySum(arr, N - 1) + arr[N - 1]);
    }

My approach towards this question is,

Step 1 -> Checking whether can you split the given array into two equal arrays. If yes next comes the Step 2 or return false without any further steps.

Step 2 -> Copying the given array elements into two different but equal arrays using recursion.

Step 3 -> Sum the newly populated two arrays and store it in two different variable.

Step 4 -> If the Sum of both the newly populated arrays is equal then the function return true else false.

Explanation :

Create two new integer arrays which are going to get populated only if the given array can be divided into two equal parts. Here it is arrA and arrB.

Check whether if the length of given array can be divided by two and have 0 remainders because this can give the answer to the question "Can this array be divided into two equal parts ?". The piece of code in this answer is arr.length % 2 == 0. If the given array satisfies this condition only then the steps given below will be carried out else it will return false.

Initialize two integer variable to store the value of Sum of both the equally divided arrays.

Initialize the two newly created arrays with the array length of half the given array which is arr.length / 2.

Then copy first half of given array elements to the first newly initialized array then the second half to the second array. To achieve this createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) method is used. arr is the argument to pass the array which should be copied to, index should be 0 because it is used as the index of newly created arrays, copyFrom is a parameter for the given array which has all the elements, copyFromIndex is used to start copying the elements from the given index.

Then calculate the sum using recursive function and store it in separate variable which was created earlier. The function used here was arraySum(int[] arr, int N).

Return whether both the sum variables are equal.

Answer 2

You were almost there. In addition to the sums, pass the number of elements:

public class Solver
{
    public static boolean canBeDividedEqually(int[] arr)
    {
        return canBeDividedEquallyHelper(arr, 0, 0, 0, 0, 0);
    }

    public static boolean canBeDividedEquallyHelper(int[] arr, int i, int nb1, int sum1, int nb2, int sum2)
    {
        if (i == arr.length)
            return nb1 == nb2 && sum1 == sum2;
        return canBeDividedEquallyHelper(arr, i+1, nb1+1, sum1 + arr[i], nb2, sum2) ||
               canBeDividedEquallyHelper(arr, i+1, nb1, sum1, nb2+1, sum2 + arr[i]);
    }

    public static void main(String[] args)
    {
        System.out.println(canBeDividedEqually(new int[]{-3, 5, -12, 14, -9, 13})); // false
        System.out.println(canBeDividedEqually(new int[]{-3, 14, 12, 5, -9, 13})); // true
    }
}

Answer 3

Try this.

static boolean canPartitioning(int[] arr) {
    return new Object() {
        int length = arr.length, half = length / 2;

        boolean partition(int i, int selected, int sum, int rest) {
            if (i >= length)
                return selected == half && sum == rest;
            return selected < half && partition(i + 1, selected + 1, sum + arr[i], rest)
                || partition(i + 1, selected, sum, rest + arr[i]);
        }
    }.partition(0, 0, 0, 0);
}


public static void main(String[] args) {
    System.out.println(canPartitioning(new int[] {-3, 5, -12, 14, -9, 13}));
    System.out.println(canPartitioning(new int[] {-3, 14, 12, 5, -9, 13}));
}

output:

false
true

Answer 4

If the change of elements order is allowed, you have to check every possible permutation of the array:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] a =  {-3, 5, -12,14,-9,13};
        int[] b =  {-3,14, 12, 5,-9,13};

        System.out.println(isEquallySplittable(a));
        System.out.println(isEquallySplittable(b));
    }

    public static boolean isEquallySplittable(int[] array){
        long arraySum = arraySum(array);
        if(arraySum % 2 != 0) return false;  //can not split an even sum by half
        return isEquallySplittable(array, 0, 0, arraySum);
    }

    public static boolean isEquallySplittable(int[] array, int indexFrom, int indexTo, long sumArray){

        if(indexTo == indexFrom) {
            indexTo++;
        }

        if(indexTo >= array.length) {
            indexTo = 0;
            indexFrom++;
        }

        if(indexFrom >= array.length)  return false;

        long sumHalfArray = arraySum(Arrays.copyOf(array, array.length/2)); //sum first half of the array
        if(sumArray  == sumHalfArray * 2 ){
            System.out.println(Arrays.toString(array) + " can be split into 2 equal arrays");
            return true;
        }
        //next permutation
        int temp = array[indexTo];
        array[indexTo] = array[indexFrom];
        array[indexFrom] = temp;
        return isEquallySplittable(array, indexFrom, ++indexTo, sumArray);
    }

    public static long arraySum(int[] arr) {
        return arraySum(arr, 0, 0);
    }

    private static long arraySum(int[] arr, int index, long sum) {
        if (index  >= arr.length ) return sum;
        sum += arr[index++];
        return arraySum(arr,index,sum);
    }
}

Answer 5

Here is Recursive solution in which elements need not be consecutive. This is simple recursive approach in which we take two lists named list1 and list2 respectively.

Then we check if it is possible to obtain a solution by adding this element in list1 (means nums[index] in context of program) if not it will check by adding the same in list2.

When the condition being true the the function recursively add element to respective list and if no solution is possible then function returns false.

The time complexity of the solution is O(2^n) as function tries each possible combination of elements adding to lists.

Here is code:

Example: int nums[] = new int[]{1, 1, 3, 4, 7};

For this resulting output would be [4, 3, 1] & [7, 1] order of elements get changed due to recursive calls.

import java.util.ArrayList;

public class SumPartition {

/**
 * These are list that stores possible sum arrays
 */
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();

public static void main(String[] args) {
    int[] arr = new int[]{1, 1, 3, 4, 7};
    SumPartition sumPartition = new SumPartition();
    if(sumPartition.sameSumArrays(arr, 0, 0, 0)) {
        System.out.println(sumPartition.list1);
        System.out.println(sumPartition.list2);
    }
    else {
        System.out.println("This is not possible");
    }
}

/**
 *
 * @param nums is array of numbers
 * @param index is index of nums array
 * @param sum1 is sum1 which is sum of elements in list1
 * @param sum2 is sum2 which is sum of elements in list2
 */
public boolean sameSumArrays(int nums[], int index, int sum1, int sum2) {

    if(index == nums.length) {
        return sum1 == sum2;
    }

    if(sameSumArrays(nums, index+1, sum1+nums[index], sum2)) {
        list1.add(nums[index]);
        return true;
    }
    else if(sameSumArrays(nums, index+1, sum1, sum2+nums[index])) {
           list2.add(nums[index]);
           return true;
    }
    return false;
}

}