解题思路

题目的本质是：

给定总预算 $budget$ 和数组 $prices$，其中每个元素表示一种奖品的价格。 要求每种奖品至少买 $1$ 件，并且总花费恰好等于 $budget$，问一共有多少种采购方案。

注意两点：

题目内容

你是一名$hr$，负责为公司年会采购商品。给定一个整数数组$prices$表示不同商品的价格，和给定的一个整数$budget$表示预算。为了保证奖品的多样性，老板要求：列表中的每种奖品至少要采购一件，需要注意的是，即使两种奖品的价格相同，它们也被视为不同的奖品，需要分别计入采购数量。在满足上述条件的前提下，剩下的预算你可以随意采购任意数量的奖品（假设每种奖品库存无限）。请你计算并返回恰好花完总预算的采购方案数，如果无法满足条件或wu f恰好凑出总预算，返回$0$）。

注意：方案仅与每种奖品购买的数量有关，与购买顺序无关。

输入描述

第一行包含一个整数 $budget$（总预算）。

第二行包含 $n$ 个整数，形成数组 $prices$，每个数之间用空格隔开。

其中：$1 \le n \le 10$，$1 \le prices[i] \le 50$，$0 \le budget \le 100$

输出描述

方案数（整型数）

样例1

输入

10
1 2

输出

4

说明

第一步：必须先买一个$1$和一个$2$，花费 $1+2=3$，剩余预算：$10-3=7$。

问题转化为：用$[1、2]$凑出$7$的组合数，方案：

$1+1+1+1+1+1+1$

$1+1+1+1+1+2$

$1+1+1+2+2$

$1+2+2+2$

输出：$4$

样例2

输入

10
5 6

输出

0

说明

第一步：必须每种商品至少买一件，花费 $5+6=11$。

此时 $11$ 已经大于总预算 $10$，无法满足基本条件，直接返回 $0$。

样例3

输入

5
1 1

输出

4

说明

设两种价格为 $1$ 商品分别为 $A$ 和 $B$。

第一步：$A$和$B$各买一件，花费 $1+1=2$，剩余预算：$5-2=3$。

问题转化为：用$1$、$1$凑出$3$的组合数，方案（仅看每种购买数量）：

额外买 $3$ 个$A$（最终 $4$个$A$，$1$个$B$）

额外买 $2$ 个$A$、$1$个$B$（最终 $3$个$A$，$2$个$B$）

额外买 $1$ 个$A$、$2$个$B$（最终 $2$个$A$，$3$个$B$）

额外买 $3$ 个$B$（最终 $1$个$A$，$4$个$B$）

输出：$4$

提示

可能存在若干种相同价格的商品，如$prices$价格如果是$[1,1]$，$budget=10$，那么 $A+9B,2A+8B,3A+7B...$整体应该是$9$种组合。