1
class Solution {
2
  double all = 0;
3

4
  public double getProbability(int[] balls) {
5
    double[] fact = new double[25];
6
    fact[0] = 1;
7
    for (int i = 1; i <= 24; i++) {
8
      fact[i] = i * fact[i - 1];
9
    }
10
    int need = Arrays.stream(balls).sum() / 2;
11
    return solve(0, 0, need, new int[balls.length], balls, fact) / all;
12
  }
13

14
  private double solve(int idx, int got, int need, int[] cur, int[] balls, double[] fact) {
15
    if (need == got) {
16
      int colors = 0;
17
      double a = fact[need];
18
      double b = fact[need];
19
      for (int i = 0; i < cur.length; i++) {
20
        if (cur[i] == balls[i]) {
21
          ++colors;
22
        } else if (cur[i] == 0) {
23
          --colors;
24
        }
25
        a /= fact[cur[i]];
26
        b /= fact[balls[i] - cur[i]];
27
      }
28
      all += a * b;
29
      return colors == 0 ? a * b : 0;
30
    }
31
    if (idx == balls.length || got > need) {
32
      return 0;
33
    }
34
    double ans = 0;
35
    for (int i = 0; i <= balls[idx]; i++) { // for this level of ball, try to take 0 to balls[idx]
36
      cur[idx] += i;
37
      ans += solve(idx + 1, got + i, need, cur, balls, fact);
38
      cur[idx] -= i;
39
    }
40
    return ans;
41
  }
42
}