HardRating 2357
1467. Probability of a Two Boxes Having The Same Number of Distinct Balls
arraymathdynamic-programmingbacktrackingcombinatoricsprobability-and-statistics
解題說明
Probability of a Two Boxes Having The Same Number of Distinct Balls
題目描述： 有 k 種顏色的球，第 i 種顏色有 balls[i] 個。將所有球隨機平均分成兩個盒子，求兩個盒子中不同顏色數量相同的機率。
解題思路： 使用回溯法（backtracking）枚舉每種顏色的球在兩個盒子中的分配方式。對於第 i 種顏色（共有 balls[i] 個球），枚舉分給第一個盒子 j 個（0 到 balls[i] 個），第二個盒子得到 balls[i]-j 個。使用多項式係數計算排列數。最後計算符合條件（兩盒不同顏色數相同）的排列數佔總排列數的比例。
C++ 解法
複雜度分析
時間複雜度：O(prod(balls[i]+1)) — 枚舉每種顏色的分配方式，最壞情況約為 O(7^8)（每種最多 6 個球，最多 8 種顏色）
空間複雜度：O(k) — 遞迴深度為顏色數 k
虛擬碼
1. Calculate total balls and half = total / 2 2. DFS backtracking over each color: a. For color i, try giving j balls (0 to balls[i]) to box 1, rest to box 2 b. Track: count in each box, distinct colors in each box, multinomial coefficient c. Prune: if either box exceeds half capacity, skip 3. At leaf (all colors assigned): if both boxes have exactly half balls: a. Add multinomial permutations to totalPerms b. If distinct colors are equal, add to validPerms 4. Return validPerms / totalPerms
其他解法
方法二：動態規劃 使用 DP 狀態 dp[i][cnt1][dist1][dist2] 表示處理完前 i 種顏色，第一個盒子有 cnt1 個球、dist1 種不同顏色，第二個盒子有 dist2 種不同顏色的方案數。空間可用滾動陣列優化。適合球數較多的情況。
方法三：數學公式直接計算 利用多項式係數和組合數直接計算。總排列數為 C(total, half)，符合條件的排列數需要枚舉所有有效的分配方式並計算多項式係數之積。
延伸思考
- 如果球不需要平均分配（兩個盒子可以有不同數量的球），如何修改解法？
- 如果要求兩個盒子中球的顏色集合完全相同（而非數量相同），解法會如何改變？
- 如何用蒙特卡羅模擬來近似估算這個機率？精確度如何保證？