牛客网 幸运的袋子

import java.util.*;
public class Main{
    //main方法里的内容还是简单的输入输出
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scanner.nextInt();
        }
        Arrays.sort(arr);
        int ret = work(arr,0,arr[0],arr[0]);//开始是从 arr[0]开始的
        System.out.println(ret);
    }
    // arr存放球球的值，len是arr的大小，pos 是当前位置，sum 当前位置的和，multi当前位置的积
    public static int work(int[] arr,int pos,int sum,int multi){
        int ret = 0;//用来记录幸运袋子的个数，也是最后的返回值
        for(int i=pos+1;i<arr.length;i++){
            sum = sum + arr[i];
            multi = multi * arr[i];
            if(sum>multi){
                //成立，继续向下进行递归
                ret = ret + 1 + work(arr,i,sum,multi);
            }else {
                //不成立，直接break
                break;
            }
            //这里进行回溯，因此要还原 sum 和 multi
            sum = sum - arr[i];
            multi = multi / arr[i];
            //还原之后 继续正常向后走
            //由于题中说 球球并无差别，因此要把相同号码的情况给排除
            while(i+1<arr.length && arr[i]==arr[i+1]){
                i++;
            }
        }
        //循环结束 也就走了(遍历)了一遍，直接返回最后的值
        return ret;
    }
}