代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

int a[101000], b[101000], n, ans = 0;int f[25050];

int readint() {
	int frog = 1, x = 0;char c = getchar();
	while(c < '0' || c > '9' ) {
		if(c == '-')
			frog = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * frog;
}

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

评测结果