题解 | #幸运的袋子#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        //幸运的袋子
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()){
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = scanner.nextInt();
            }
            //用数组存储好每个球的大小
            //对数组进行排序，减小计算次数
            Arrays.sort(arr);
            System.out.println(count(arr, n, 0, 0, 1));

        }
    }
    //递归求幸运袋子数,参数，开始位置，sum，muty值，
    public  static int count(int[] a,int n,int pos,int sum,int muty){
        int count =0;
        //遍历求和求积
        for (int i = pos; i < n; i++) {
            sum+=a[i];
            muty*=a[i];
            if (sum>muty){
                //递归求下一层，开始位置加一
                count = count+1 + count(a,n,i+1,sum,muty);
            }else if(a[i]==1){
                //当等于1时，说明后面的也有可能是幸运的袋子
                count = count+count(a,n,i+1,sum,muty);

            }else if (sum<=muty){
                //此时说明不是幸运的袋子，由于排序了，
                // 所以后面的球数也不可能，结束进行回溯
                break;
            }
            sum = sum-a[i];
            muty /=a[i];
            //如果是相同的球号就跳过
            while (i <n-1&&a[i]==a[i+1]){
                i++;
            }
        }
        return count;
    }

}