Estoy tratando de escribir un método que devuelva verdadero si es posible dividir todos los miembros de una matriz en dos grupos diferentes de igual tamaño para que la suma de los miembros de los dos grupos sea igual. Si esto no es posible, el método Return false.
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){ }Me quedé atascado aquí y no tengo ni idea de qué hacer a continuación.
Hice este código pero no verifica todas las posibilidades, pero creo que es un buen comienzo:
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) ; }algo como esto debería resolver su problema y manejar todos los casos.
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); }