解题思路

dfs加剪枝。 有重复元素的全排列公式如下：

$$\frac{(\sum_{i=1}^{k} s_i)!}{ \Pi_{i} s_i!}$$

然后枚举两个箱子中，每个球的个数。分别求出两个箱子中的排列数，乘积相加，就是分子。

一共有8种球，每种球的个数是0-6，最多的状态数为$7^8 = 5764801$ 在可接受的范围内

每个最终的状态，判断球的颜色的个数是不是相等，然后计算即可。

再向下走的时候，如果发现某个箱子中的球的个数超过了全部球的一半，则可以直接剪枝。

个人博客

C++代码

class Solution {
public:
    vector<int> left, right, bas;
    int ln = 0, rn = 0;
    int alls = 0;
    double tot, ak;

    double fac(int a){   // 求阶乘
        double ans = 1;
        for(int i = 1; i <= a; i ++) ans *= i;
        return ans;
    }

    double get(vector<int>& bas){   // 求排列数
        int n = 0;
        for(auto x:bas) n += x;
        double ans = fac(n);
        for(auto x:bas) ans /= fac(x);
        return ans;
    }


    void dfs(int i){
        if(ln > alls / 2 || rn > alls / 2) return ;  // 剪枝
        if(i == left.size()){   // 叶子节点
            // for(auto x:left) cout << x << " ";
            // cout << endl;
            // for(auto x:right) cout << x <<" ";
            // cout << endl;
            int a = 0, b = 0;
            for(auto x:left){
                if(x) a ++;
            }
            for(auto x:right){
                if(x) b ++;
            }
            if(a == b)   // 两个箱子中的球的颜色种类相同
                ak += get(left) * get(right);
            return;
        }
        for(int j = 0; j <= bas[i]; j++){   // 枚举当前颜色球，左右箱子中的个数
            left[i] = j;    
            right[i] = bas[i] - j;
            ln += j;   // 记录两个箱子中球的总数，用于剪枝
            rn += bas[i] - j;
            dfs(i + 1);   // 递归调用
            ln -= j;   // 恢复现场
            rn -= bas[i] - j;
        }
    }

    double getProbability(vector<int>& balls) {

        bas = balls;
        left = vector<int>(balls.size(), 0);
        right = vector<int>(balls.size(), 0);
        tot = get(balls);   // 求分母
        for(auto x:balls) alls += x;   
        dfs(0);  // 求分子
        // cout << ak << " " << tot << endl;
        return ak / tot; 
    }
};