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
|
|
Example 2
|
|
Example 3
|
|
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
- For each color, decide how many balls go to box1 (the rest go to box2).
- Track the number of balls and distinct colors in each box.
- Use factorials to count the number of ways for each valid distribution.
- The answer is the ratio of valid ways to total ways.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.