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 <= 81 <= balls[i] <= 6sum(balls) is even.Problem Overview: You are given an array where balls[i] represents the number of balls of color i. All balls are randomly split into two boxes with the same total number of balls. The goal is to compute the probability that both boxes end up containing the same number of distinct colors.
Approach 1: Backtracking with Combinatorics (Exponential time, O(k) space)
Enumerate every valid way to distribute balls of each color between the two boxes while ensuring both boxes end with exactly total/2 balls. For each color i, iterate from 0..balls[i] to decide how many go to box A and place the rest in box B. Track three values during recursion: balls count in each box, number of distinct colors in each box, and the number of permutations for that configuration. Use factorial-based combinations (C(n, k)) to count how many permutations each distribution contributes. If both boxes have the same number of distinct colors, add its permutations to the valid count. The probability equals valid_permutations / total_permutations. This approach relies on combinatorics to count arrangements and backtracking to explore distributions. Time complexity is roughly O(∏(balls[i] + 1)) which is manageable because the number of colors is small (≤ 8). Space complexity is O(k) for recursion depth.
Approach 2: Dynamic Programming with Combinatorics (O(k * n^3) time, O(n^3) space)
Instead of enumerating every distribution explicitly, model the process as a DP over colors. Let the state track: how many balls are placed in box A, how many distinct colors appear in box A, and how many appear in box B after processing the first i colors. For each color, try all splits of its balls between the two boxes and update the DP using the number of ways given by C(balls[i], split). Precompute factorials to evaluate combinations quickly. At the end, sum all states where both boxes contain total/2 balls and the distinct color counts match. This reduces repeated recomputation from brute enumeration and uses dynamic programming to aggregate counts efficiently. Time complexity is approximately O(k * n^3), where k is the number of colors and n is half the total balls. Space complexity is O(n^3) for the DP table.
Recommended for interviews: The backtracking + combinatorics approach is the most common explanation because it directly models the distribution process and demonstrates strong understanding of counting and probability. Interviewers expect you to combine recursion with factorial-based combination counting. The DP version is useful when discussing optimization and overlapping subproblems, but most candidates solve the problem using backtracking with careful combinatorics.
The backtracking approach systematically explores all possible ways of distributing the balls into two boxes, tracking how the number of distinct colors emerges in each box. At each step, we decide how many balls of a particular color to place into the first box, and calculate how many would consequently be in the second box. This process is repeated recursively, allowing us to enumerate all possible distributions. Then, we count how many distributions end up with an equal number of distinct colors in both boxes.
This Python code uses recursion with backtracking to iterate over all possible ways to distribute the balls into two boxes. The function tracks the number of balls in each box and their distinct colors. It computes the probability of distributing the balls so that both boxes have the same number of distinct colors. The solution balances the division of each color between boxes during recursion, calculating the probability by dividing the number of successful distributions by the total number of ways to split the balls into two halves.
Python
JavaScript
Time Complexity: O(k * 2^k), where k is the number of different colors. This is due to recursion over k colors with varied combinations.
Space Complexity: O(k) due to the recursion stack.
This approach employs dynamic programming to optimize recursive calculations. By building a memoization table, we track and reuse results of subproblems, reducing redundancies. The key lies in calculating the number of ways to allocate the balls into two boxes while maintaining counts of distinct colors. By storing outcomes for subarrays of the ball array, the dynamic programming solution dramatically cuts down on recomputation, yielding an efficient algorithm.
This C++ code is structured around dynamic programming principles, storing intermediate results for efficient reuse. The recursive dfs function pilots color distribution between two boxes, adjusting counts of distinct colors involved. By leveraging a multidimensional lookup table, the program avoids redundant calculations and directly extracts results from previously computed subproblems. It ultimately determines the probability of getting equal distinct counts in both boxes.
Time Complexity: O(k * n^2 * k^2), where k is the number of colors, and n is half the total number of balls.
Space Complexity: O(k * n^2 * k^2) due to dynamic programming storage.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(k * 2^k), where k is the number of different colors. This is due to recursion over k colors with varied combinations. |
| Dynamic Programming Approach | Time Complexity: O(k * n^2 * k^2), where k is the number of colors, and n is half the total number of balls. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Combinatorics | O(∏(balls[i]+1)) | O(k) | Best for understanding the distribution logic and typical interview explanations. |
| Dynamic Programming with Combinatorics | O(k * n^3) | O(n^3) | Useful when optimizing repeated calculations or discussing DP state transitions. |
Probability of a Two Boxes Having The Same Number of Distinct Balls | Leetcode | Weekly challenge • Roshan Srivastava • 1,825 views views
Watch 5 more video solutions →Practice Probability of a Two Boxes Having The Same Number of Distinct Balls with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor