题解 | #神奇的口袋#

• DFS

  采用void型

  不论当前是否查找成功，都要继续递归，不可直接终止，遍历所有可能

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int sum;//方法数
int n;//物品数
int v[21];//物品体积
bool visit[21];//访问标记
void dfs(int curv,int pos){
    if(curv==40){
        sum++;
        return ;
    }
    for(int i=pos;i<n;i++){
        if(curv+v[i]>40||visit[i])continue;
        visit[i]=true;
        dfs(curv+v[i],i+1);//无论成功或者失败都要继续下一次循环
        visit[i]=false;
    }
    return ;
}

int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&v[i]);
        }
        sum=0;
        memset(visit, false, sizeof(visit));
        dfs(0,0);
        printf("%d\n",sum);
    }
    return 0;
}