1
/**
2
 * @param {number[]} balls
3
 * @return {number}
4
 */
5
var getProbability = function (balls) {
6
  var k = balls.length;
7
  var halfUsed = balls.reduce((acc, val) => acc + val, 0) / 2;
8
  var startArray = new Array(k);
9
  startArray.fill(0);
10

11
  const perm = function (b1, b2) {
12
    var p1, p2, s1, s2;
13

14
    s1 = b1.reduce((acc, val) => acc + val, 0);
15
    s2 = b2.reduce((acc, val) => acc + val, 0);
16

17
    const fact = function (n) {
18
      var f = 1;
19
      for (let i = 2; i <= n; i++) f *= i;
20
      return f;
21
    };
22

23
    p1 = fact(s1);
24
    p2 = fact(s2);
25

26
    b1.forEach((val) => {
27
      if (val > 1) p1 /= fact(val);
28
    });
29
    b2.forEach((val) => {
30
      if (val > 1) p2 /= fact(val);
31
    });
32

33
    return p1 * p2;
34
  };
35

36
  const getValidCombos = function (ballsUsed, colorNum = 0) {
37
    var box1Used = ballsUsed.reduce((acc, val) => acc + val, 0);
38
    var matches = { good: 0, total: 0 },
39
      thisColorMax = halfUsed - box1Used;
40

41
    if (colorNum === k - 1) {
42
      /* 
43
                               Last ball color - adjust # of balls of this color to equal half
44
                               (if possible).  Then count # of different balls in each box.
45
                       */
46
      if (thisColorMax > balls[colorNum]) return { good: 0, total: 0 };
47

48
      ballsUsed[colorNum] = thisColorMax;
49
      let ballsLeft = [];
50
      let colorsUsed = [0, 0];
51
      for (let i = 0; i < k; i++) {
52
        ballsLeft[i] = balls[i] - ballsUsed[i];
53
        if (ballsUsed[i] > 0) colorsUsed[0]++;
54
        if (ballsLeft[i] > 0) colorsUsed[1]++;
55
      }
56

57
      /* Count the # of permutations for the boxes represented by this 1 combination. */
58
      let permutations = perm(ballsUsed, ballsLeft, k);
59
      return {
60
        good: colorsUsed[1] === colorsUsed[0] ? permutations : 0,
61
        total: permutations,
62
      };
63
    }
64

65
    thisColorMax = Math.min(thisColorMax, balls[colorNum]);
66
    for (let i = 0; i <= thisColorMax; i++) {
67
      let match = getValidCombos([...ballsUsed], colorNum + 1);
68
      matches = {
69
        good: matches.good + match.good,
70
        total: matches.total + match.total,
71
      };
72
      ballsUsed[colorNum]++;
73
    }
74
    return matches;
75
  };
76

77
  /* Probability = (total # of permutations with equal # of balls) / (permutations with same # of unique balls) */
78
  let res = getValidCombos(startArray);
79
  return res.good / res.total;
80
};