题解 | #神奇的口袋#

//参考高赞的方法，用分治法。修改了部分代码，便于理解
#include <iostream>
using namespace std;

int count(int target_limit,int v[],int index){
    if(target_limit==0){
        return 1;
    }
    if(target_limit<0||index<0){
        return 0;
    }
    return count(target_limit,v,index-1)+count(target_limit-v[index],v,index-1);
}

int main() {
    int n;
    while (cin>>n) {
        int v[21];
        for(int i=0;i<n;i++){
            cin>>v[i];
        }
        int target_limit=40;
        cout<<count(target_limit,v,n)<<endl;
    }
}