设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 

问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。 

如果有满足条件的选择，则此背包有解，否则此背包问题无解。

 

输入

输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）

多组测试数据。

输出

对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“

样例输入

20 51 3 5 7 9

样例输出

YES

#include 
      
       int g_value[1000];int packet(int weight, int mount){if (weight == 0)  //背包问题有解{return 1;  }if (weight < 0 || (weight > 0 && mount < 1))  //此背包集合不符合条件{return 0;}if (packet(weight - g_value[mount - 1], mount - 1))  //判断是否 weight[mount - 1]是否包含在最后的背包集合中{return 1;    //在}else{return packet(weight, mount - 1);  //不在}}int main(){int weight, mount, i;while(EOF != scanf("%d%d", &weight, &mount)){for (i = 0; i < mount; i++){scanf("%d", &g_value[i]);}if (packet(weight, mount)){printf("YES\n");}else{printf("NO\n");}}return 0;}