<p>You are given an integer array <code>nums</code>.</p>

<p>You should move each element of <code>nums</code> into one of the two arrays <code>A</code> and <code>B</code> such that <code>A</code> and <code>B</code> are non-empty, and <code>average(A) == average(B)</code>.</p>

<p>Return <code>true</code> if it is possible to achieve that and <code>false</code> otherwise.</p>

<p><strong>Note</strong> that for an array <code>arr</code>, <code>average(arr)</code> is the sum of all the elements of <code>arr</code> over the length of <code>arr</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7,8]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 30</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int tsum;
    int n;
    int cum[31];
    bool f(vector<int> &nums, vector<vector<vector<bool>>> &dp, int i, int size, int sum) {
        // if states are out of bounds the ans is not possible hense return false
        if((i < 0) or (size < 0) or (sum < 0)) 
            return false;
        // we initialized dp with true values hense if the state is false we can be sure that is's been calculated
        if(dp[i][size][sum]==false) 
            return false;
        // if size is zero and we have achieved target sum we return true, other wise we return false coz we can't recruite further elements to get targeted sum
        if(size == 0) 
            return dp[i][size][sum] = (sum==0);
        // if targeted sum is achieved but size is not zero then we need the zero elements in nums to fill in for remaining size needed. hense if remaining zeroes are greater then or equal to size then true else if not sufficient number of zeroes then false
        if(sum == 0) 
            return dp[i][size][sum] = (cum[i] >= size);
        // we have 2 choice at idx i, take it or leave it xD
        return dp[i][size][sum] = f(nums, dp, i-1, size-1, sum-nums[i]) or f(nums, dp, i-1, size, sum);
    }
    bool splitArraySameAverage(vector<int>& nums) {
        n = nums.size();
        tsum = accumulate(nums.begin(), nums.end(), 0); // total sum of the array
        
        // 3d - dp array 
        // dim 0: starting position in array from which we need the requred sum in given size
        // dim 1: size of the array in which required sum is to be fit
        // dim 2: remaining sum
        
        vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n+1, vector<bool>(tsum+1, true)));
        cum[0] = (nums[0]==0);
        
        // store number of zeros from index 0 to i in cum array
        for(int i=1; i<n; i++) {
            if(nums[i]) {
                cum[i]=cum[i-1];
            } else {
                cum[i]=cum[i-1]+1;
            }
        }
        // do not be confused with my fency temp it is just product of size and total sum (i.e. tsum * size here)
        // one thing to be noted is both array must be non empty so the chosen array is to be of size 1 to n-1 period
        int temp = 0;
        for(int size=1; size<n; size++) {
            temp+=tsum;
            if((temp%n==0) and f(nums, dp, n-1, size, temp/n)) {return true;}
        }
        return false;
    }
};
192718