题解 | #幸运的袋子#

import java.util.*;

/**
 * 解题步骤如下：
 * 1. 将原号码从小到大排序
 * 2. 从第一个号码开始穷举，其中穷举的终止条件是当前号码与前面的号码无法组成幸运的袋子，且当前号码不为 1
 *    此时就直接返回即可，因为数组已经是排好序的，后面的数字只会越来越大。
 * 3. 进行下一个循环的时候，要把 sum 和 multi 的值均恢复
 * 特殊情况：1. 当当前号码为 1 的时候，尽管 sum <= multi,也要继续向下一层列举，只是本次不算幸运的袋子
 *         2. 循环列举的时候记得去除相同的号码的重复统计
 */
public class Main {
    //穷举
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] number = new int[n];
        for (int i = 0; i < n; i++) {
            number[i] = scanner.nextInt();
        }
        //从小到大排序
        Arrays.sort(number);
        System.out.println(getCount(number,0,0,1));
    }

    /**
     * 穷举出 number 中的号码中符合幸运的袋子的条件的号码组合
     * @param number  号码数组（从小到大排好序的）
     * @param index   当前穷举的起始下标
     * @param sum     之前袋子中号码的总和
     * @param multi   之前袋子中号码的总积
     * @return
     */
    private static int getCount(int[] number, int index, int sum, int multi) {
        int count = 0;
        for (int i = index; i < number.length; i++) {
            sum += number[i];
            multi *= number[i];
            if (sum > multi) {
                count += 1 + getCount(number,i+1,sum,multi);
            } else if (number[i] == 1) {
                count += getCount(number,i+1,sum,multi);
            } else {
                break;
            }
            //恢复 sum 和 multi 的值
            sum -= number[i];
            multi /= number[i];
            //去除重复的号码
            while (i < number.length-1 && number[i] == number[i+1]) {
                i++;
            }
        }
        return count;
    }
}