## Algorithm

Problem Name: 805. Split Array With Same Average

You are given an integer array `nums`.

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

Return `true` if it is possible to achieve that and `false` otherwise.

Note that for an array `arr`, `average(arr)` is the sum of all the elements of `arr` over the length of `arr`.

Example 1:

```Input: nums = [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 an average of 4.5.
```

Example 2:

```Input: nums = [3,1]
Output: false
```

Constraints:

• `1 <= nums.length <= 30`
• `0 <= nums[i] <= 104`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````start coding...
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int sum = 0, n = A.size();
for (int& x: A) {
sum += x;
}
sort(A.rbegin(), A.rend());
for (int i = 1; i  < = n/2; ++i) {
if (sum*i%n == 0 && dfs(A, 0, i, sum*i/n, n)) {
return true;
}
}
return false;
}

bool dfs(vector<int>& A, int pos, int count, int target, int& n) {
if (count == 0) {
return target == 0;
}
if (pos == n || target > A[pos] * count) {
return false;
}

for (int i = pos; i  <  n; ++i) {
if (target >= A[i] && dfs(A, i + 1, count - 1, target - A[i], n)) {
return true;
}
}
return false;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,5,6,7,8]

Output

cmd
true

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const splitArraySameAverage = function(A) {
const totalSum = A.reduce((ac, el) => ac + el, 0)
const len = A.length
const mid = Math.floor(len / 2)
A.sort((a, b) => b - a)
for (let i = 1; i  < = mid; i++) {
if ((totalSum * i) % len === 0 && combinationSum(A, 0, i, (totalSum * i) / len)) return true
}
return false
}

function combinationSum(nums, idx, k, target) {
if (target > k * nums[idx]) return false
if (k === 0) return target === 0
for (let i = idx; i  <  nums.length - k; i++) {
if (nums[i] <= target && combinationSum(nums, i + 1, k - 1, target - nums[i])) return true
}
return false
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,5,6,7,8]

Output

cmd
true

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def splitArraySameAverage(self, A):
def find(target, k, i):
if (target,k) in not_found and not_found[(target,k)] <= i: return False
if k == 0: return target == 0
if k + i > len(A): return False
res = find(target - A[i], k - 1, i + 1) or find(target, k, i + 1)
if not res: not_found[(target, k)] = min(not_found.get((target, k), n), i)
return res
not_found = dict()
n, s = len(A), sum(A)
return any(find(s * i / n, i, 0) for i in range(1, n // 2 + 1) if s * i % n == 0)
``````
Copy The Code &

Input

cmd
nums = [3,1]

Output

cmd
false