题解 | #神奇的口袋#

深度遍历，做排序预处理进行剪枝

#include <iostream>
#include <algorithm>
using namespace std;
int res=0;
int n;
void dfs(int p[],int iter ,int num){
    if(num>40||iter>=n){
        return;
    }
    //选p[iter]
    if(p[iter]+num>40){//之后的只会更大
        return;
    }
    else if(p[iter]+num==40){
        res++;    
    }
    else{
        dfs(p,iter+1,num+p[iter]);      
    }
    //不选p[iter]
    dfs(p,iter+1,num);
}
int main() {
    
    cin>>n;
    int *p=new int[n];bool *visit=new bool[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
        visit[i]=false;
    }
    sort(p,p+n);dfs(p,0,0);
    cout<<res<<endl;
}
// 64 位输出请用 printf("%lld")