1
class Solution {
2
  public boolean splitArraySameAverage(int[] nums) {
3
    int n = nums.length, sum = Arrays.stream(nums).sum();
4
    Set<Integer>[] a = new HashSet[n / 2 + 1];
5
    Set<Integer>[] b = new HashSet[n / 2 + 2];
6
    Arrays.setAll(a, o -> new HashSet<>());
7
    Arrays.setAll(b, o -> new HashSet<>());
8
    gen(0, n / 2, 0, 0, nums, a);
9
    gen(n / 2, n, 0, 0, nums, b);
10
    for (int i = 0; i < a.length; i++) { // i = num of elements selected from A
11
      for (int j = 0; j < b.length; j++) { // j = num of elements selected from B
12
        if (i + j > 0 && i + j < n && sum * (i + j) % n == 0) {
13
          for (int cur : a[i]) { // do Two Sum
14
            if (b[j].contains(sum * (i + j) / n - cur)) {
15
              return true;
16
            }
17
          }
18
        }
19
      }
20
    }
21
    return false;
22
  }
23

24
  private void gen(int cur, int n, int bits, int sum, int[] nums, Set<Integer>[] set) {
25
    set[bits].add(sum);
26
    if (cur < n) {
27
      gen(cur + 1, n, bits + 1, sum + nums[cur], nums, set);
28
      gen(cur + 1, n, bits, sum, nums, set);
29
    }
30
  }
31
}