双深度优先搜索题解｜第一个做出来这道题的

dfs1枚举出移除的m个砝码，dfs2枚举可能的重量。因数据量小(n<20)，双重dfs不会超时。

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

const int N = 25;
int n, m;
int a[N];
bool flag[N];
int mx = 0;

void dfs2(int u, int sum, set<int>& s) {
    if (u == n + 1) {
        if (sum != 0) {
            s.insert(sum);
        }
        return;
    }
    if (flag[u]) {
        dfs2(u + 1, sum, s);
    } else {
        dfs2(u + 1, sum, s);
        dfs2(u + 1, sum + a[u], s);
    }
}

void dfs1(int u, int x) {
    if (u > m) {
        set<int> s;
        dfs2(1, 0, s);
        mx = max(mx, (int)s.size());
        return;
    }
    for (int i = x + 1; i <= n; i++) {
        if (!flag[i]) {
            flag[i] = true;
            dfs1(u + 1, i);
            flag[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dfs1(1, 0);
    cout << mx;
}