#607. wjr 的背包问题

wjr 的背包问题

说明


wjr 最近在学习动态规划的经典问题————背包问题

题目是这样的:总共有 n 种物品,每种物品的数量有无限个,每种物品有一个体积 a_i

现在 wjr 已经选出了 m 个物品,并且程序输出了一个结果表示已经选的物品体积总和

但是他不知道自己的程序是否正确

于是他想知道, m 种物品有多少种可能的体积之和?

他希望你可以告诉他所有的可能性,并且按照升序从小到大输出

输入格式

第一行两个整数,分别表示 n,m

接下来一行 n 个数,第 i 个数表示 a_i 表示每种物品的体积

对于 20% 的数据,n,m <= 30

对于 50% 的数据,n,m <= 100

对于 100% 的数据,n,m,a_i <= 500

输出格式

按照升序顺序输出所有可能的体积之和

样例

3 3 
2 3 5
6 7 8 9 10 11 12 13 15