题解 | 神奇的口袋

#include <iostream>
using namespace std;
int n,weight=0,res=0;
int obj[25];
bool visit[25];

void dfs(int o){
    if(weight==40){
        res++;
        return;
    }
    if(weight>40){
        return;
    }
    for(int i=o;i<n;i++){
        if(!visit[i]){
            weight+=obj[i];
            visit[i]=true;
            dfs(i+1);
            visit[i]=false;
            weight-=obj[i];
        }
    }
}

int main() {
    while (cin >> n) { 
        res=weight=0; //遇到新的案例重置全局变量；
        for(int i=0;i<n;i++)visit[i]=false;

        for(int i=0;i<n;i++){
            cin>>obj[i];
        }
        dfs(0);
        cout<<res;
    }
}
// 64 位输出请用 printf("%lld")

【思路】：深搜dfs

【关键点分析01】：

当你选择了第i个物品后，递归调用应该是dfs(i+1)，而不是dfs(o+1)。

• 假设o=0，第一次循环i=0选中物品 0，此时下一层递归应该从i=1开始（即dfs(1)）
• 但你写的dfs(o+1)会导致下一层递归从o+1=1开始，看似正确？其实有问题！

问题出在多轮选择时：

• 当第一次递归o=0，选中i=2时，下一层应该从3开始
• 但dfs(o+1)会让下一层从1开始，导致重复计算（比如会重新考虑i=1的物品）

【关键点分析02】：

在这段代码中，for(int i = o; i < n; i++) 中的 i = o 并不是固定为 i = 0，而是 i 初始化为当前递归函数的参数 o 的值。

这个 o 的值是动态变化的，它代表「当前递归层级中，允许选择的物品起始索引」，目的是避免重复计算相同的组合。

举个例子理解：

• 第一次调用 dfs(0) 时，o = 0，所以 i 从 0 开始循环（可以选择第 0 个、第 1 个... 第 n-1 个物品）。
• 当选择了第 i=2 个物品后，递归调用应该是 dfs(i+1) 即 dfs(3)，此时下一层循环中 i 会从 3 开始（只能选择第 3 个及以后的物品）。

这样设计的核心逻辑是：

每个物品只能在「它之后的物品」被选择，从而保证组合的唯一性（例如 [1,2] 和 [2,1] 会被视为同一个组合，只计算一次）。

如果写成 i = 0 而不是 i = o，会导致：

• 每次递归都从第 0 个物品开始判断，同一个组合会被反复计算（比如先选 1 再选 2，和先选 2 再选 1 会被算成两种）。
• 最终结果会远大于正确答案。