蒜头君去书店买书，他有 m 元钱，书店里面有 n 本书，每本书的价格为

pi元。蒜头君很爱学习，想把身上钱都用来买书，并且刚好买 k 本书。请帮蒜头君计算他是否能刚好用 m 元买 k 本书。

输入格式

第一行输入

33 个整数 m(1≤m≤100000000)，n(1≤n≤30)，k(1≤k≤min(8,n))

接下来一行输入 n 个整数，表示每本书的价格 (1≤p i ≤100000000)。

输出格式

如果蒜头君能 刚好 用 m 元买 k 本书，输入一行"Yes", 否则输出"No"。

样例输入1

10 4 4

1 2 3 4样例输出1

Yes

样例输入2

10 4 3

1 2 3 4样例输出2

No

解题思路：抽象形式的dfs和剪枝。如何进行搜索？例如：一共有1 2 3 4

1. 1取还是不取，分为两种情况，取和不取
2. 在取的情况下判断2 取还是不取
3. 在不取的情况下判断2取还是不取
4. 依次类推

如何剪枝：

1. 当k==0&∑==m
2. k==0
3. sum<=m
4. 记录开始的位置避免镜像重复，例如从1，2中取俩书，12，21重复了。

#include
    
     #include
     
      #include
      
       using namespace std;int v[31];//记录每本书的价格int flag[31];//记录每本书当前状态是否被选//n:一共n本书，k:取k本书，m:题目要求刚好的价格,sum:已选书的价格//start:为了优化，例如从1,2取俩本书，12,21重复了void dfs(int n,int k,int m,int sum,int start){    if(k==0&&sum==m){cout<<"Yes";exit(0);}//如果正好第k本，一共m价格，输出    if(k==0)    return ;//如果没有m元，且已经去了k本，返回    if(sum>=m)  return ;//如果还没取到k本时，就超过或等于m元时，返回。                for(int i=start;i<=n;++i){        if(flag[i]==1)  continue;                sum+=v[i];        flag[i]=1;//更新sum，将书的状态设置为已选                dfs(n,k-1,m,sum,i+1);                flag[i]=0;//回溯        sum-=v[i];    }}int main(){    int m,n,k;    cin>>m>>n>>k;    k=min(8,k);    for(int i=1;i<=n;++i)    cin>>v[i];        dfs(n,k,m,0,1);    cout<<"No";//如果程序能运行到这里且没退出，即无法找到}