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.

Examples

Example 1

1
2
3
4
5
6
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

1
2
3
4
5
6
7
8
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

1
2
3
4
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.

Solution

Method 1 – Backtracking with Combinatorics

Intuition

We can use backtracking to try all ways to distribute balls into two boxes, counting the number of ways where both boxes have the same number of distinct colors. We use combinatorics to count arrangements efficiently.

Approach

  1. For each color, decide how many balls go to box1 (the rest go to box2).
  2. Track the number of balls and distinct colors in each box.
  3. Use factorials to count the number of ways for each valid distribution.
  4. The answer is the ratio of valid ways to total ways.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
    double getProbability(vector<int>& balls) {
        int n = accumulate(balls.begin(), balls.end(), 0) / 2, k = balls.size();
        vector<double> fact(49, 1);
        for (int i = 1; i < 49; ++i) fact[i] = fact[i-1] * i;
        double valid = 0, total = 0;
        function<void(int,int,int,int,int,int)> dfs = [&](int i, int c1, int c2, int d1, int d2, double ways) {
            if (i == k) {
                if (c1 == n && c2 == n) {
                    total += ways;
                    if (d1 == d2) valid += ways;
                }
                return;
            }
            for (int x = 0; x <= balls[i]; ++x) {
                int y = balls[i] - x;
                dfs(i+1, c1+x, c2+y, d1+(x>0), d2+(y>0), ways / (fact[x] * fact[y]));
            }
        };
        dfs(0,0,0,0,0,fact[accumulate(balls.begin(), balls.end(), 0)]);
        return valid / total;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import "math"
func getProbability(balls []int) float64 {
    n, k := 0, len(balls)
    for _, b := range balls { n += b }
    n /= 2
    fact := make([]float64, 49)
    fact[0] = 1
    for i := 1; i < 49; i++ { fact[i] = fact[i-1] * float64(i) }
    var valid, total float64
    var dfs func(i, c1, c2, d1, d2 int, ways float64)
    dfs = func(i, c1, c2, d1, d2 int, ways float64) {
        if i == k {
            if c1 == n && c2 == n {
                total += ways
                if d1 == d2 { valid += ways }
            }
            return
        }
        for x := 0; x <= balls[i]; x++ {
            y := balls[i] - x
            dfs(i+1, c1+x, c2+y, d1+boolToInt(x>0), d2+boolToInt(y>0), ways/(fact[x]*fact[y]))
        }
    }
    dfs(0,0,0,0,0,fact[sum(balls)])
    return valid / total
}
func sum(a []int) int { s := 0; for _, v := range a { s += v }; return s }
func boolToInt(b bool) int { if b { return 1 }; return 0 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
class Solution {
    public double getProbability(int[] balls) {
        int n = Arrays.stream(balls).sum() / 2, k = balls.length;
        double[] fact = new double[49];
        fact[0] = 1;
        for (int i = 1; i < 49; ++i) fact[i] = fact[i-1] * i;
        double[] valid = new double[1], total = new double[1];
        dfs(balls, 0, 0, 0, 0, 0, fact, valid, total, n);
        return valid[0] / total[0];
    }
    private void dfs(int[] balls, int i, int c1, int c2, int d1, int d2, double[] fact, double[] valid, double[] total, int n) {
        if (i == balls.length) {
            if (c1 == n && c2 == n) {
                double ways = fact[2*n];
                for (int j = 0; j < balls.length; ++j) ways /= fact[balls[j]];
                total[0] += ways;
                if (d1 == d2) valid[0] += ways;
            }
            return;
        }
        for (int x = 0; x <= balls[i]; ++x) {
            int y = balls[i] - x;
            dfs(balls, i+1, c1+x, c2+y, d1+(x>0?1:0), d2+(y>0?1:0), fact, valid, total, n);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    fun getProbability(balls: IntArray): Double {
        val n = balls.sum() / 2
        val k = balls.size
        val fact = DoubleArray(49) { 1.0 }
        for (i in 1 until 49) fact[i] = fact[i-1] * i
        var valid = 0.0
        var total = 0.0
        fun dfs(i: Int, c1: Int, c2: Int, d1: Int, d2: Int, ways: Double) {
            if (i == k) {
                if (c1 == n && c2 == n) {
                    total += ways
                    if (d1 == d2) valid += ways
                }
                return
            }
            for (x in 0..balls[i]) {
                val y = balls[i] - x
                dfs(i+1, c1+x, c2+y, d1+if (x>0) 1 else 0, d2+if (y>0) 1 else 0, ways/(fact[x]*fact[y]))
            }
        }
        dfs(0,0,0,0,0,fact[balls.sum()])
        return valid / total
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List
import math
class Solution:
    def getProbability(self, balls: List[int]) -> float:
        n = sum(balls) // 2
        k = len(balls)
        fact = [1.0]
        for i in range(1, 49):
            fact.append(fact[-1] * i)
        valid = total = 0.0
        def dfs(i, c1, c2, d1, d2, ways):
            nonlocal valid, total
            if i == k:
                if c1 == n and c2 == n:
                    total += ways
                    if d1 == d2:
                        valid += ways
                return
            for x in range(balls[i]+1):
                y = balls[i] - x
                dfs(i+1, c1+x, c2+y, d1+(x>0), d2+(y>0), ways/(fact[x]*fact[y]))
        dfs(0,0,0,0,0,fact[sum(balls)])
        return valid / total
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
impl Solution {
    pub fn get_probability(balls: Vec<i32>) -> f64 {
        let n: i32 = balls.iter().sum::<i32>() / 2;
        let k = balls.len();
        let mut fact = vec![1.0f64; 49];
        for i in 1..49 { fact[i] = fact[i-1] * (i as f64); }
        let mut valid = 0.0;
        let mut total = 0.0;
        fn dfs(i: usize, c1: i32, c2: i32, d1: i32, d2: i32, ways: f64, balls: &Vec<i32>, n: i32, k: usize, fact: &Vec<f64>, valid: &mut f64, total: &mut f64) {
            if i == k {
                if c1 == n && c2 == n {
                    *total += ways;
                    if d1 == d2 { *valid += ways; }
                }
                return;
            }
            for x in 0..=balls[i] {
                let y = balls[i] - x;
                dfs(i+1, c1+x, c2+y, d1+if x>0 {1} else {0}, d2+if y>0 {1} else {0}, ways/(fact[x as usize]*fact[y as usize]), balls, n, k, fact, valid, total);
            }
        }
        dfs(0,0,0,0,0,fact.iter().take((2*n+1) as usize).product(), &balls, n, k, &fact, &mut valid, &mut total);
        valid / total
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    getProbability(balls: number[]): number {
        const n = balls.reduce((a, b) => a + b, 0) / 2;
        const k = balls.length;
        const fact = [1.0];
        for (let i = 1; i < 49; ++i) fact.push(fact[fact.length-1] * i);
        let valid = 0, total = 0;
        function dfs(i: number, c1: number, c2: number, d1: number, d2: number, ways: number) {
            if (i === k) {
                if (c1 === n && c2 === n) {
                    total += ways;
                    if (d1 === d2) valid += ways;
                }
                return;
            }
            for (let x = 0; x <= balls[i]; ++x) {
                const y = balls[i] - x;
                dfs(i+1, c1+x, c2+y, d1+(x>0?1:0), d2+(y>0?1:0), ways/(fact[x]*fact[y]));
            }
        }
        dfs(0,0,0,0,0,fact[balls.reduce((a,b)=>a+b,0)]);
        return valid / total;
    }
}

Complexity

  • ⏰ Time complexity: O((n/2)^k) where k is the number of colors and n is the total number of balls. The number of states is exponential in k.
  • 🧺 Space complexity: O(k) for recursion stack and factorials.