题解 | #神奇的口袋#

//采用递归的思想(dfs)
#include "stdio.h"
int N;
int count;//记录解决方案个数
int array[30];//记录物品重量
bool isUesd[30];//记录物品被选择情况，false为未选择
void calculate(int weight,int pos){//weight为当前还剩的重量,pos为上一个物品的下标
    if(weight == 0){
        ++count;
        return;
    }
    for (int i = pos; i < N; ++i) {//要从pos开始，不然会多算情况。而且这样并不少算情况
        if(isUesd[i] == false){    //因为要选择的几样物品必然可以通过从前到后的次序选择出来
            isUesd[i] = true;//拿去array[i]
            calculate(weight - array[i],i);
            isUesd[i] = false;//算完后还要放回array[i]
        }
    }
    return;
}

int main(){
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        scanf("%d",array+i);
        isUesd[i] = false;
    }
    calculate(40,0);
    printf("%d",count);
}