回溯

这道题数据范围比较小，所以直接搜索就能过。但有一个地方感觉得注意一下，就看那组测试用例，说明所给集合中是有重复元素的，按说20+20=40，也就是三个物品中任选两个价值都是40，其实这是同一种组合方式，如果单从理论上来说还需要再剪枝来去掉重复组合的（要先排序），但是这道题目中每个物品是有实际含义的，价值虽然一样但代表的是不同物品，所以(20,20)就对应了三种不同的组合，这样一来这道题就很简单了，不需要考虑任何其他情况，挨个位置搜一遍就行了。

#include<bits/stdc++.h>
using namespace std;

const int N = 50;
int v[N];
int n, res;

int sum = 0;
void dfs(int idx)
{
    if(sum >= 40)
    {
        if(sum == 40)
            res++;
        return;
    }
    for(int i = idx; i < n; i++)
    {
        sum += v[i];
        dfs(i + 1);
        sum -= v[i];
    }
}

int main()
{
    //法二：回溯暴搜，就是最简单的组合问题
    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];

    dfs(0);

    cout << res << endl;

    return 0;
} ** ** ** **** ** ** **