代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=105;
int n,a[N];
bool f[25005];

int main() {
    int T;
    for(scanf("%d",&T);T--;) {
        scanf("%d",&n);
        int mx=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),mx=mx>a[i]?mx:a[i];
        std::sort(a+1,a+n+1);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=0;
        for(int i=1;i<=n;++i) {
            if(!f[a[i]]) {
                ++ans;
                for(int j=a[i];j<=mx;++j) f[j]|=f[j-a[i]];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

评测结果