Split Array With Same Average

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:


Solution:

class Solution {
    
    public boolean splitArraySameAverage(int[] A) {
        int sum = 0;
        for (int a : A) { 
            sum += a;
        }
        Integer[][] dp = new Integer[sum + 1][A.length + 1];
        dp[0][0] = 0;
        double target = (double) (sum) / A.length;
        for (int i = 1; i <= A.length; i ++) {
            int curr = A[i - 1];
            for (int j = curr; j <= sum; j ++) {
                if (dp[j - curr][i - 1] != null) {
                    int prevLen = dp[j - curr][i - 1];
                    dp[j - curr][i] = prevLen;
                    dp[j][i] = prevLen + 1;
                    if (dp[j][i] < A.length && (double) (j) / dp[j][i] == target) {
                        return true;
                    }
                }
            }
        }
        // for (Integer[] arr : dp) System.out.println(Arrays.toString(arr));
        return false;
    }
}