# Probability of a Two Boxes Having The Same Number of Distinct Balls
**Difficulty:** HARD
[External](https://leetcode.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls)
Canonical: https://scaleengineer.com/dsa/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
**Data structures:** Array
---
## Problem
Given `2n` balls of `k` distinct colors. You will be given an integer array `balls` of size `k` where `balls[i]` is the number of balls of color `i`.

All the balls will be **shuffled uniformly at random**, then we will distribute the first `n` balls to the first box and the remaining `n` balls to the other box (Please read the explanation of the second example carefully).

Please note that the two boxes are considered different. For example, if we have two balls of colors `a` and `b`, and two boxes `[]` and `()`, then the distribution `[a] (b)` is considered different than the distribution `[b] (a) `(Please read the explanation of the first example carefully).

Return _the probability_ that the two boxes have the same number of distinct balls. Answers within `10-5` of the actual value will be accepted as correct.

**Example 1:**

**Input:** balls = [1,1]
**Output:** 1.00000
**Explanation:** Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

**Example 2:**

**Input:** balls = [2,1,1]
**Output:** 0.66667
**Explanation:** We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equal probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that, we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

**Example 3:**

**Input:** balls = [1,2,1,2]
**Output:** 0.60000
**Explanation:** The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

**Constraints:**

* `1 <= balls.length <= 8`
* `1 <= balls[i] <= 6`
* `sum(balls)` is even.

# Approaches
## Recursive Backtracking
This approach uses a recursive (backtracking) function to explore all possible ways to distribute the balls of each color between the two boxes. For each complete distribution configuration (defined by the number of balls of each color in box 1), it checks if the number of distinct colors in both boxes is the same. If it is, the number of ways to form that specific distribution is calculated and added to a running total of favorable outcomes. The final probability is this total divided by the total number of ways to partition the balls.
**Time:** O(product(balls[i]+1)). The recursion tree explores all combinations of distributing balls for each color. In the worst case (`balls[i]=6` for all `k=8` colors), this is roughly `7^8`, which can be slow. · **Space:** O(k), where `k` is the number of colors. This space is used by the recursion stack.
**Pros:** Conceptually straightforward, as it directly models the combinatorial counting process.; Relatively easy to implement.
**Cons:** Can be slow due to recomputing results for the same subproblems. The state `(idx, count1, dist1, dist2)` might be reached through different paths.; The time complexity is exponential in the number of colors, which might be too slow if the constraints were larger.
### Explanation
The problem asks for the probability of an event, which is the ratio of favorable outcomes to total outcomes. The total number of ways to distribute `2n` balls into two boxes of size `n` is equivalent to choosing `n` balls for the first box, which is `C(2n, n)`.

The core of this approach is to count the number of favorable distributions. A distribution is favorable if both boxes have the same number of distinct colors. We can find this by exploring all possible ways to distribute the balls of each color.

A recursive function `countFavorable(colorIndex, ballsInBox1, distinctColorsBox1, distinctColorsBox2)` can be designed. This function calculates the number of ways to distribute balls from `colorIndex` to the end, given the current state of the two boxes.

- The state is defined by `colorIndex` (which color we are distributing), `ballsInBox1` (current number of balls in box 1), `distinctColorsBox1` (distinct colors in box 1), and `distinctColorsBox2` (distinct colors in box 2).
- The function iterates from `i = 0` to `balls[colorIndex]`, where `i` is the number of balls of the current color to place in box 1. The remaining `balls[colorIndex] - i` balls go to box 2.
- For each `i`, we update the state and make a recursive call for the next color. The number of ways for this specific choice is `C(balls[colorIndex], i)`. This is multiplied by the result from the recursive call, and these products are summed up.
- The base case is when all colors are distributed. We check if the conditions for a favorable outcome are met (`ballsInBox1 == n` and `distinctColorsBox1 == distinctColorsBox2`).

Finally, we divide the total favorable ways by the total ways `C(2n, n)` to get the probability.

```java
class Solution {
    double[][] C;
    int[] balls;
    int k, n;

    public double getProbability(int[] balls) {
        this.balls = balls;
        this.k = balls.length;
        int totalBalls = 0;
        for (int b : balls) {
            totalBalls += b;
        }
        this.n = totalBalls / 2;

        // Precompute combinations C(n, k) for small n (up to 6)
        this.C = new double[7][7];
        for (int i = 0; i < 7; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }

        double favorableOutcomes = countFavorable(0, 0, 0, 0);
        double totalOutcomes = combinations(totalBalls, n);

        return favorableOutcomes / totalOutcomes;
    }

    private double countFavorable(int idx, int count1, int dist1, int dist2) {
        if (idx == k) {
            return (count1 == n && dist1 == dist2) ? 1.0 : 0.0;
        }

        double ans = 0.0;
        // i balls of color idx go to box 1
        for (int i = 0; i <= balls[idx]; i++) {
            if (count1 + i > n) {
                break;
            }
            
            double waysForChoice = C[balls[idx]][i];
            
            ans += waysForChoice * countFavorable(
                idx + 1, 
                count1 + i, 
                dist1 + (i > 0 ? 1 : 0), 
                dist2 + (i < balls[idx] ? 1 : 0)
            );
        }
        return ans;
    }

    // Helper for C(n, k) for large n
    private double combinations(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1.0;
        if (k > n / 2) k = n - k;
        double res = 1.0;
        for (int i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
}
```
### Algorithm
- Calculate `n`, which is half the total number of balls (`sum(balls) / 2`).
- Create a helper function to calculate combinations `C(n, k)`. Since `balls[i]` is small, we can precompute these values. For calculating the total ways, `C(2n, n)`, a separate function that handles larger numbers using floating-point arithmetic is needed.
- Define a recursive function, let's call it `countFavorable(colorIndex, ballsInBox1, distinctColorsBox1, distinctColorsBox2)`.
- **Base Case:** When `colorIndex` reaches the total number of colors (`k`), check if `ballsInBox1 == n` and `distinctColorsBox1 == distinctColorsBox2`. If both conditions are met, this path represents a valid set of distributions, so return `1.0`. Otherwise, return `0.0`.
- **Recursive Step:** For the current `colorIndex`, iterate through all possible numbers of balls (`i`) to place in the first box, from `0` to `balls[colorIndex]`.
  - Prune the search if `ballsInBox1 + i > n`.
  - The number of ways to choose `i` balls of the current color is `C(balls[colorIndex], i)`.
  - Make a recursive call for the next color: `countFavorable(colorIndex + 1, ballsInBox1 + i, distinctColorsBox1 + (i > 0 ? 1 : 0), distinctColorsBox2 + (i < balls[colorIndex] ? 1 : 0))`.
  - Multiply the result of the recursive call by `C(balls[colorIndex], i)` and add it to a running total for the current function call.
- The initial call to the function will be `countFavorable(0, 0, 0, 0)`.
- The final probability is the total favorable ways returned by the initial call divided by the total possible ways to choose `n` balls, which is `C(2n, n)`.

## Backtracking with Memoization (Dynamic Programming)
This approach enhances the recursive backtracking solution by using memoization to avoid redundant computations. A multi-dimensional array is used to store the results of subproblems that have already been solved. This technique, also known as top-down dynamic programming, transforms the exponential time complexity of the naive recursion into a polynomial time solution, making it much more efficient and suitable for the given constraints.
**Time:** O(k * n * k * k * max(balls[i])). The number of states is `k * n * k * k`. Each state is computed once, and its computation involves a loop of size at most `max(balls[i])`. This is a polynomial time complexity. · **Space:** O(k * n * k * k) for the memoization table. Given the constraints `k<=8, n<=24`, this is `8 * 24 * 8 * 8`, which is feasible. An additional `O(k)` is used for the recursion stack.
**Pros:** Significantly more efficient than plain recursion due to avoiding recomputations.; Guaranteed to be fast enough for the given constraints.; Maintains the logical clarity of the recursive solution.
**Cons:** Requires extra space for the memoization table, which can be significant depending on the constraints.
### Explanation
The plain recursive solution suffers from re-calculating the same subproblems multiple times. For example, the state `(colorIndex=2, ballsInBox1=5, ...)` might be reached via different distributions of the first two colors. Memoization is the perfect optimization for this.

We define the state of our recursion by `(idx, count1, dist1, dist2)`. The result for this state is the number of ways to favorably complete the distribution from this point onwards. We can store these results in a 4D array `memo[k+1][n+1][k+1][k+1]`.

When the recursive function `countFavorable(idx, count1, dist1, dist2)` is called, it first checks if `memo[idx][count1][dist1][dist2]` has already been computed. If so, it returns the stored value. Otherwise, it proceeds with the calculation as in the simple recursive approach. Once the result is computed, it's stored in the memoization table before being returned. This guarantees that the code for each state is executed only once.

This optimization drastically reduces the number of computations, making the solution very efficient and well within the time limits for the problem's constraints.

```java
class Solution {
    double[][][][] memo;
    double[][] C;
    int[] balls;
    int k, n;

    public double getProbability(int[] balls) {
        this.balls = balls;
        this.k = balls.length;
        int totalBalls = 0;
        for (int b : balls) {
            totalBalls += b;
        }
        this.n = totalBalls / 2;

        // Memoization table initialized with -1
        this.memo = new double[k + 1][n + 1][k + 1][k + 1];
        for (double[][][] d3 : memo) {
            for (double[][] d2 : d3) {
                for (double[] d1 : d2) {
                    java.util.Arrays.fill(d1, -1.0);
                }
            }
        }

        // Precompute combinations C(n, k) for small n
        this.C = new double[7][7];
        for (int i = 0; i < 7; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }

        double favorableOutcomes = countFavorable(0, 0, 0, 0);
        double totalOutcomes = combinations(totalBalls, n);

        return favorableOutcomes / totalOutcomes;
    }

    private double countFavorable(int idx, int count1, int dist1, int dist2) {
        if (idx == k) {
            return (count1 == n && dist1 == dist2) ? 1.0 : 0.0;
        }
        if (memo[idx][count1][dist1][dist2] != -1.0) {
            return memo[idx][count1][dist1][dist2];
        }

        double ans = 0.0;
        for (int i = 0; i <= balls[idx]; i++) {
            if (count1 + i > n) {
                break;
            }
            
            double waysForChoice = C[balls[idx]][i];
            
            ans += waysForChoice * countFavorable(
                idx + 1, 
                count1 + i, 
                dist1 + (i > 0 ? 1 : 0), 
                dist2 + (i < balls[idx] ? 1 : 0)
            );
        }
        return memo[idx][count1][dist1][dist2] = ans;
    }

    private double combinations(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1.0;
        if (k > n / 2) k = n - k;
        double res = 1.0;
        for (int i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
}
```
### Algorithm
- The algorithm is fundamentally the same as the plain recursive backtracking approach.
- An additional data structure, a memoization table (e.g., a multi-dimensional array `memo`), is used to store the results of subproblems.
- The state of a subproblem is defined by the tuple `(colorIndex, ballsInBox1, distinctColorsBox1, distinctColorsBox2)`.
- Before computing the result for a state in the recursive function, check if the result is already present in the `memo` table. If yes, return the stored value immediately.
- If the result is not in the table, compute it as in the backtracking approach.
- After computing the result, store it in the `memo` table before returning it. This ensures that each unique subproblem is solved only once.
- The rest of the logic, including calculating combinations and the final probability, remains the same.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  long[][] c;
private
  int[] balls;
private
  Map<List<Integer>, Long> f = new HashMap<>();
public
  double getProbability(int[] balls) {
    int mx = 0;
    for (int x : balls) {
      n += x;
      mx = Math.max(mx, x);
    }
    n >>= 1;
    this.balls = balls;
    int m = Math.max(mx, n << 1);
    c = new long[m + 1][m + 1];
    for (int i = 0; i <= m; ++i) {
      c[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      }
    }
    return dfs(0, n, 0) * 1.0 / c[n << 1][n];
  }
private
  long dfs(int i, int j, int diff) {
    if (i >= balls.length) {
      return j == 0 && diff == 0 ? 1 : 0;
    }
    if (j < 0) {
      return 0;
    }
    List<Integer> key = List.of(i, j, diff);
    if (f.containsKey(key)) {
      return f.get(key);
    }
    long ans = 0;
    for (int x = 0; x <= balls[i]; ++x) {
      int y = x == balls[i] ? 1 : (x == 0 ? -1 : 0);
      ans += dfs(i + 1, j - x, diff + y) * c[balls[i]][x];
    }
    f.put(key, ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double getProbability(vector<int> &balls) {
    int n = accumulate(balls.begin(), balls.end(), 0) / 2;
    int mx = *max_element(balls.begin(), balls.end());
    int m = max(mx, n << 1);
    long long c[m + 1][m + 1];
    memset(c, 0, sizeof(c));
    for (int i = 0; i <= m; ++i) {
      c[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      }
    }
    int k = balls.size();
    long long f[k][n + 1][k << 1 | 1];
    memset(f, -1, sizeof(f));
    function<long long(int, int, int)> dfs = [&](int i, int j,
                                                 int diff) -> long long {
      if (i >= k) {
        return j == 0 && diff == k ? 1 : 0;
      }
      if (j < 0) {
        return 0;
      }
      if (f[i][j][diff] != -1) {
        return f[i][j][diff];
      }
      long long ans = 0;
      for (int x = 0; x <= balls[i]; ++x) {
        int y = x == balls[i] ? 1 : (x == 0 ? -1 : 0);
        ans += dfs(i + 1, j - x, diff + y) * c[balls[i]][x];
      }
      return f[i][j][diff] = ans;
    };
    return dfs(0, n, k) * 1.0 / c[n << 1][n];
  }
};

```

### Python

```python
class Solution:
    def getProbability(self, balls: List[int]) -> float: @ cache def dfs(i: int, j: int, diff: int) -> float: if i >= k: return 1 if j == 0 and diff == 0 else 0 if j < 0: return 0 ans = 0 for x in range(balls[i] + 1): y = 1 if x == balls[i] else (- 1 if x == 0 else 0) ans += dfs(i + 1, j - x, diff + y) * comb(balls[i], x) return ans n = sum(balls) >> 1 k = len(balls) return dfs(0, n, 0) / comb(n << 1, n)

```