Split Array With the Same Average

The idea here is that for each element you have 2 options (like in a Knapsack problem), select the ninja member in B or A. The sum of strengths of ninjas in team B is the sum of numbers in B and n is the number of elements in B. The states can’t be uniquely classified by just ‘i’ and sum because you can obtain the same sum value by selecting a different number of elements, which will affect the average.

Assume we split the total ninjas (let list (array) ‘strengths’ denote the list of strengths of the total ninjas given to us) into ‘A’ and ‘B’ so that avg(A) == avg(B).

Notice a fact that in this problem we have: avg(strengths) == avg(A) == avg(B)

So we only need to find a proper subset B such that avg(B) == avg(strengths) and we can just put the remaining elements in A.

Now if avg(B)==avg(strengths), that means sum(B) / B.length == sum(strengths) / N

or, sum(B) == sum(strenghts) * B.length / N

That means we need to find a subset B, such that its sum and length satisfies this condition.

The algorithm will be:

1. We will initialise a dictionary ‘DP’ (for faster lookups) which would have the values of whether the selected subsets would result into a sum that we require.
2. We will use a subfunction that checks if the total ‘K’ elements sums to a ‘TARGET’ value in each iteration. Here, ‘TARGET’ is the goal, ‘K’ is the number of elements in set ‘B’, while ‘i’ is the index we have traversed through so far.
3. Inititalise ‘N’ with the total length of the strengths of ninjas given and ‘S’ with the sum of total strengths given in the list.
4. Now for we iterate for each possible length ‘j’ of subset ‘B’ from length 1 to length ‘N’ // 2 + 1 and we check if we can find targetSum ‘S’ * ‘j’ // ‘N’ (total sum of j elements that sums to s*j//n) for each function call (named: ‘FIND’) we will check:
   • If we are down searching for ‘K’ elements in the array, see if the ‘TARGETSUM’ is 0 or not, which would be the basecase.
   • If the to-be selected elements in ‘B[K]’ + elements we have traversed so far is larger than total length of A, even if we choose all elements, we don't have enough elements left, there should be no valid answer.
   • If there is already a calculated value for the (TARGET, K, i) in the ‘DP’ dictionary we directly return that as DP[(TARGET, K, i)]
   • Otherwise, we calculate the ith element by:
     • DP[(TARGETSUM - STRENGTHS[i], K - 1, i + 1)] = find(TARGETSUM - STRENGTHS[i], k-1, i + 1) or find(TARGETSUM, K, i + 1)
5. Atlast we will return True if any of those subsets are found in the function otherwise we return False.

O(N^2 * SUM), where N denotes the number of elements in the list and ‘SUM’ is the sum of the array.

We are initialising a 3D array and may have to calculate all the possible outcomes whether the selected subsets would result into a sum that we require. Thus, the time complexity due to it will be O(N^2 * SUM).

O(N^2 * SUM), where N denotes the number of elements in the list and ‘SUM’ is the sum of the array.

We are using a 3D array of size (N^2 * SUM) to store the all the possible outcomes possible which is possible and can be required during recursion. Thus, the space complexity due to the array/list will be O(N^2 * SUM).