计蒜客习题：买书

---

问题描述

蒜头君去书店买书，他有 m 元钱，书店里面有 n 本书，每本书的价格为 pi元。蒜头君很爱学习，想把身上钱都用来买书，并且刚好买 k 本书。请帮蒜头君计算他是否能刚好用 m 元买 k 本书。
输入格式
第一行输入 33 个整数 m(1≤m≤100000000)，n(1≤n≤30)，k(1≤k≤min(8,n))
接下来一行输入 n 个整数，表示每本书的价格pi(1≤pi≤100000000)。
输出格式
如果蒜头君能 刚好 用 m 元买 k 本书，输入一行”Yes”, 否则输出”No”
样例输入
10 4 3
1 2 3 4
样例输出
No

---

AC代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int p[100];         //记录价格
int sz = 0;         //p的大小
int dfs(int cur,int xuan,int rest,int num){
  if (rest < 0 || num <0 )
    return 0;           //判断结尾
  else if (rest == 0 && num == 0)
  {cout<<"Yes";exit(0);}  
  else if (cur == sz - 1)
    return 0; //判断是否满足
  else {
    dfs(cur + 1, 0, rest, num);
    dfs(cur + 1, 1, rest - p[cur], num - 1);
    }
    return 0;
}
int main()
 {
  int m, n, k;
  cin >> m >> n >> k; //输入
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x <= m)
      p[sz] = x;
    sz++;
  }
  dfs(0, 0, m, k);
  dfs(0, 1, m - p[0], k - 1);
    cout << "No";
  return 0;
 }