题目

桌面上有 2n 个颜色不完全相同的球，球的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。

注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。

请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10-5 以内，则被视为正确答案

示例 1：

输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：
- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
  - 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
    这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
示例 2：

  输入：balls = [2,1,1]
  输出：0.66667
  解释：球的列表为 [1, 1, 2, 3]
  随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 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]
  然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。
  这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
  概率 = 8/12 = 0.66667

示例 3：

  输入：balls = [1,2,1,2]
  输出：0.60000
  解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
  概率 = 108 / 180 = 0.6 。

提示：

• 1 <= balls.length <= 8
• 1 <= balls[i] <= 6
• sum(balls) 是偶数

思路

dfs

解法

class Solution {
    double res=0,total;
    double[] A;
    private boolean check(int[] pre,int[] last){
        int a=0,b=0;
        for(int i=0;i<pre.length;i++){
            if(pre[i]!=0) a++;
            if(last[i]!=0) b++;
        }
        //if(a==b) System.out.println("ok");
        return a==b;
    }
    private double com(int[] a){
        double cnt=1;
        for(int i:a){
            if(i!=0) { 
                cnt=cnt*A[i];
            }
        }
        return cnt;
    }
    private void dfs(int n,int cur,int[] pre,int[] last,int tar){
        if(cur==pre.length||n==0){
            if(n==0){
                double cnt=A[tar]*A[tar];
                cnt/=com(pre);
                cnt/=com(last);
                if(check(pre,last)) res+=cnt;
                total+=cnt;
            }
            return;
        }
        for(int j=0;j<=last[cur]&&j<=n;j++){
                last[cur]-=j;
                pre[cur]+=j;
                dfs(n-j,cur+1,pre,last,tar);
                pre[cur]-=j;
                last[cur]+=j;    
        }
    }
    public double getProbability(int[] balls) {
        res=0;
        total=0;
        int sum=0;
        A=new double[30];
        A[0]=1;
        for(int i=1;i<=24;i++) A[i]=A[i-1]*i;
        for(int i:balls) sum+=i;
        int n=balls.length;
        int[] pre=new int[n];
        dfs(sum/2,0,pre,balls,sum/2);
        //System.out.println(res+" "+total);
        return (double)(res*1.0/total);
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现