1
class Solution {
2
 public:
3
  double c[7][7] = {}, v = 0, tc = 0;
4
  int t = 0;
5
  void solve(int idx, int k1, int k2, int n1, double p, vector<int> &balls) {
6
    if (idx == size(balls)) {
7
      if (n1 == t) {
8
        v += (k1 == k2) * p;
9
        tc += p;
10
      }
11
    } else {
12
      int k11, k12;
13
      for (int i = 0; i <= balls[idx]; ++i) {
14
        if (i + n1 > t) break;
15
        k11 = k1 + (i > 0);
16
        k12 = k2 + (balls[idx] - i > 0);
17
        solve(idx + 1, k11, k12, n1 + i, p * c[balls[idx]][i], balls);
18
      }
19
    }
20
  }
21
  double getProbability(vector<int> &balls) {
22
    for (int i = 0; i <= 6; ++i) {
23
      c[i][0] = c[i][i] = 1;
24
      for (int j = 1; j < i; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
25
    }
26
    for (auto &i : balls) t += i;
27
    t /= 2;
28
    solve(0, 0, 0, 0, 1, balls);
29
    return v / tc;
30
  }
31
};