题解 | #幸运的袋子#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {
        string line;
        while ((line = System.Console.ReadLine ()) != null) { // 注意 while 处理多个 case
            int n = int.Parse(line);
            line = Console.ReadLine();
            string[] t = line.Split(' ');
            ulong[] ball = new ulong[t.Length];
            for(int i = 0; i < t.Length; i++) ball[i] = ulong.Parse(t[i]);
            //排序ball
            for(int i = 0; i < ball.Length; i++){
                bool swap = false;
                for(int j = 0; j < ball.Length - 1 - i; j++){
                    if(ball[j] > ball[j+1]){
                        ulong temp = ball[j];
                        ball[j] = ball[j+1];
                        ball[j+1] = temp;
                        swap = true;
                    }
                }
                if(!swap) break;
            }
            //递归遍历所有情况
            Console.WriteLine(recursion(0,ball,0,1));
        }    
    }
    //递归加球，每次加球只列举从index开始，每种各加1个的情况，不会出现一次递归加了两个一样的球
    public static int recursion(int index, ulong[] ball, ulong sum, ulong pro){
        int count = 0;
        while(index < ball.Length){
            sum += ball[index];
            pro *= ball[index];
            if(sum > pro) 
                count += 1 + recursion(index + 1, ball, sum, pro);
            else if(ball[index] == 1)
                count += recursion(index + 1, ball, sum, pro);
            else
                return count;
            ulong temp = ball[index];
            sum -= temp;
            pro /= temp;
            //定位到下一种球的位置
            while(++index < ball.Length){
                if(ball[index] != temp) 
                    break;
            }
        }
        return count;
    }
}

我们不从口袋里拿出球，而是把球一个一个放进口袋，并判断是否是幸运袋子。

为了遍历所有情况而不出现重复，我们举个例子：

对于1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,3,3,3,3,7,7,7

第一个球可以拿

1;2;3;7

第二次拿可以变成

1,1; 1,2; 1,3; 1,7;

2,2; 2,3; 2,7;

3,3; 3,7;

7,7;

我们发现显然第一次拿2的情况下，第二次不可以再拿1，因为2,1和 1,2是一样的

所以我们第i次拿的时候，只需要考虑从i-1次拿的球开始拿

代码思路：

先对ball数组从小到大排序，定义一个递归，它从index处开始拿球，列举第i次可以拿的球的情况，若某种情况下，是幸运袋子，那么count++，调用自身，拿第i+1次；若不满足，有两种情况：1.是在拿第一个球，且第一个球是1，那么我们拿这个球，然后调用自身拿下一个；2.不是第一个球，那么没有再往大的球拿的必要了，因为拿x不是幸运袋子，拿比x大的更不是，直接return count；