题解

#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
const int inf = 5000005;
int f[25005];
int a[105];
int i, j, n, T, ans;
int main() {
    ios::sync_with_stdio(false);

    cin >> T;
    while (T--) {
        memset(f, 0, sizeof(f));
        cin >> n;
        ans = n;
        for (i = 1; i <= n; i++) { cin >> a[i]; }
        sort(a + 1, a + n + 1);
        f[0] = 1;
        for (i = 1; i <= n; i++) {
            if (f[a[i]]) {
                ans--;
                continue;
            }
            for (j = a[i]; j <= a[n]; j++) {
                f[j] = f[j] | f[j - a[i]];
            }
        }
        cout << ans << endl;
    }
    return 0;
}