Boolean recursive static method that gets an array of integers

user_9351897 0
Viewed 397

I'm trying to write a method that would Return true if it is possible to divide all the members of an array into two different groups of equal size so that the sum of the members of the two groups is equal. If this is not possible, the method Return false.

The conditions are:

  • The method should be recursive with no use of loops at all, So are all the auxiliary methods Can not contain loops.
  • The array is neither null nor empty.
  • Do not modify the contents of the array (not even temporarily), and do not use an auxiliary array.
public static boolean equalSplit (int[] arr){
    if(arr.length % 2 != 0) // if array length is not equal both sides
        return false;
    return equalSplit (arr, arr[0],(0 + arr.length-1) / 2 , arr.length-1);
} 

public static boolean equalSplit (int[] arr, int start, int mid, int end){
       
}

I got stuck here and i have no clue what to do next.

java
2 Answers

I made this code but it doesn't check all possibilities , but I think its a good start :

public static boolean equalSplit (int[] arr){
    if(arr.length % 2 != 0) // if array length is not equal both sides
        return false;

    return equalSplit (arr, 0 ,(0 + arr.length-1) / 2 , arr.length-1 , 0 , 0);
}


public static boolean equalSplit (int[] arr, int start, int mid, int end,int sumStart,int sumEnd){
    if(start == mid){// both sides have the same iterations
        return sumEnd == sumStart ;
    }
    sumStart += arr[start];
    sumEnd += arr[end];
    start ++;
    end--;
    return equalSplit ( arr, start, mid, end ,sumStart , sumEnd) ;
}
user_146294580

something like this should solve your problem and handle all cases.

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

    }

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

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

    private static boolean canBeDividedEqually(int[] arr, int sum) {
        // this can be optimized by canBeDividedEqually(arr, sum/2, arr[0], arr.length/2, 1, 1) because first element should always belong to first group, so we can start search from second element
        return canBeDividedEqually(arr, sum/2, 0, arr.length/2, 0, 0);
//        return canBeDividedEqually(arr, sum/2, arr[0], arr.length/2, 1, 1);
    }

    private static boolean canBeDividedEqually (int[] arr, int searchSum, int currentSum, int searchQuantity, int currentQuantity, int nextIndex) {
        if(searchSum == currentSum && searchQuantity == currentQuantity) {
            return true;
        }
        if(searchSum <= currentSum || searchQuantity <= currentQuantity) {
            // we have too big sum or we take to much elements
            return false;
        }
        if(nextIndex + (searchQuantity - currentQuantity) > arr.length) {
            // we need to take more elements than we have still available
            return false;
        }
        // add current element into account and search further
        if(canBeDividedEqually(arr, searchSum, currentSum + arr[nextIndex], searchQuantity, currentQuantity + 1, nextIndex + 1)) {
            System.out.println("true");
            return true;
        }
        // if above "if" statement is not true, then skip current element and try to search further
        return canBeDividedEqually(arr, searchSum, currentSum, searchQuantity, currentQuantity, nextIndex + 1);
    }
user_83079200
Related