题面描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团。为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

思路

这是一个典型的子集和问题，需要找到所有代表团的子集，使得这些代表团的人数之和恰好等于汽车的容量。由于代表团可能有相同的人数，但它们是不同的代表团，因此需要考虑每个代表团的唯一性。

使用动态规划（DP）来解决这个问题。定义 dp[i][j] 为前 i 个代表团中，选取一些代表团使得人数之和为 j 的方案数。状态转移方程为：

题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束:

一个团只能上一辆车，并且代表团人数 (代表团数量小于 $30$ ，每个代表团人数小于 $30$ )小于汽车容量(汽车容量小于 $100$ )

需要将车辆坐满

输入描述

第一行 代表团人数，英文逗号隔开，代表团数量小于 $30$ ，每个代表团人数小于 $30$

第二行 汽车载客量，汽车容量小于 $100$

输出描述

坐满汽车的方案数量，如果无解输出 $0$

样例1

输入

5,4,2,3,2,4,9
10

输出

4

说明

解释 以下几种方式都可以坐满车，所以，优先接待输出为 $4$

$[2,3,5]$

$[2,4,4]$

$[2,3,5]$

$[2,4,4]$