题解 | #神奇的口袋#

//这题DFS只需要void
//迷迷糊糊地就做出来了.......
#include<cstring>
#include <iostream>
using namespace std;
int goods[20];
int visit[20];
int n;
int num;
void DFS(int xb,int contain)//当前物品的下标，当前口袋的容积
{
    
    for(int i=xb;i<=n-1;i++)
    {
        int ncontain=contain+goods[i];
        if(visit[i]||ncontain>40)continue;

        visit[i]=true;
        if(ncontain==40)
        {
            DFS(0,0);
            num++;
        }
        else
        {
            DFS(i+1,ncontain);
        }
        visit[i]=false;
    }

}


int main() {
    
    while (cin >> n) { 
        num=0;
        for(int i=0;i<n;i++)
        {
            cin>>goods[i];
        }
        memset(visit,false,sizeof(visit));
        DFS(0,0);
        cout<<num<<endl;
    }
}