Probability of a Two Boxes Having The Same Number of Distinct Balls — LeetCode 1467 Python Solution

The 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.

Example

Input

balls = [1,1]

Output

1.00000

Explanation

Only 2 ways to divide the balls equally:

Python solution

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)

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems