神奇的口袋

回溯算法模板

result =  []
void backtrack(路径,选择列表)
    if 满足结束条件
        result.add(路径)
        return 

    for 选择 in 选择列表 do
        做选择
        backtrack(路径,选择列表)
        撤销选择

AC代码

#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 21;
int n;//n代表不同的物品的数目
int ans = 0;
bool vis[maxn] = {false};
void backtrack(int item[], int k, int sum){
    if(sum == 40){
        ans++;
        return;
    }
    // 求解空间第i个位置上的下一个解
    for(int i = k; i < n; i++){
        if(vis[i] || sum + item[i] > 40) continue;
        vis[i] = true;//做选择
        backtrack(item, i, sum + item[i]);// backtrack(路径,选择列表)
        vis[i] = false; //撤销选择
    }
}
int main(){
    scanf("%d", &n);
    int item[maxn];

    for(int i = 0; i < n; i++){
        scanf("%d", &item[i]);
    }

    sort(item, item + n);
    int k, sum;//k记录当前选择物品数目，sum记录当前选择物品总体积
    backtrack(item, 0, 0);
    printf("%d\n", ans);
    return 0;
}