2020-08-19 小A点菜

https://www.luogu.com.cn/problem/P1164

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;

long long qmi(int m, int k)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t;
        t = t * t;
        k >>= 1;
    }
    return res;
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

#define maxn 1005

int n,m;
int food[maxn];
int ans = 0;
int cnt = 0;//计算钱数
void deepfound(int i){
    cnt += food[i];
    
    if(cnt > m||i > n){
        return ;
    }
    
    if(cnt == m){//刚好用完
        ans++;//方案数++
        return;
    }
    
    for (int j = i+1; j <=n ;  j++) {//查找下一个方案
        deepfound(j);
        cnt -= food[j];
    }
}

int main(){
    //输入菜的种类，口袋钱数
    n = read();
    m = read();
    
    for(int i = 1 ; i <= n ; i++){
        food[i] = read();
    }
    
    for(int i = 1 ; i <= n ; i++){
        deepfound(i);
        cnt = 0;
    }
    
    cout<<ans<<endl;
    return 0;
}
/*
4 4
1 1 2 2
============
10
*/