深度优先搜索

蒜头君去书店买书，他有 m 元钱，书店里面有 n 本书，每本书的价格为
pi元。蒜头君很爱学习，想把身上钱都用来买书，并且刚好买 k 本书。请帮蒜头君计算他是否能刚好用 m 元买 k 本书。

输入格式

第一行输入
3
3 个整数 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<iostream>
#include<cstdio>
#include<algorithm>
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";//如果程序能运行到这里且没退出，即无法找到
}