Java实现 LeetCode 805 数组的均值分割 （DFS+分析题）

805. 数组的均值分割

给定的整数数组 A ，我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。（B数组和C数组在开始的时候都为空）

返回true ，当且仅当在我们的完成这样的移动后，可使得B数组的平均值和C数组的平均值相等，并且B数组和C数组都不为空。

示例:

输入:

[1,2,3,4,5,6,7,8]

输出: true

解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

注意:

A 数组的长度范围为 [1, 30].

A[i] 的数据范围为 [0, 10000].

PS：

这个题是求能不能进行平均分组，我们可以把题目转换成模拟一个组所有的值得和

因为要求是俩个组得平均值相等，也就是所有人得平均值都要相等

DFS寻找每一次得可能，知道找到

class Solution {
//两组的平均值相等的话，证明我所有的和的平均值是相等的
public boolean splitArraySameAverage(int[] A) {
int sum = 0;
for (int num : A) {
sum += num;
}
//Asum / len = Bsum / i = Csum / len - i
int len = A.length;
Arrays.sort(A);
for (int i = 1; i <= len / 2; i++) {
if (sum * i % len == 0) {
//是否存在长度为i 的 sum和为 sum * i / len B arr
if (dfs(A, i, sum * i / len, 0)){
return true;
}
}
}
return false;
}
private boolean dfs(int[] A, int n, int targetSum, int startIndex) {
if (targetSum == 0 && n == 0) {
return true;
}
if (n != 0) {
for (int i = startIndex; i < A.length; i++) {
if (i > startIndex && A[i] == A[i - 1]) {
continue;
}
if (dfs(A, n - 1, targetSum - A[i], i + 1)) {
return true;
}
}
}
return false;
}
}