一维迭代解法

解题思路:
与一楼的思路一致，但因为用set会超时，所以采用了以下方法优化

参考代码:

#include<bits/stdc++.h>

using namespace std;

int n;

int g[100005],cut=0,ans;

int main(){

cin>>n;

for(int i=1;i<=n;i++){

int w;

cin>>w;

cut++;

if(g[w]==0) g[w]=cut;

for(int j=1;j<100005;j++){

if(g[j]>0&&g[j]<cut){

if(g[j+w]==0) g[j+w]=cut;

if(g[abs(j-w)]==0) g[abs(j-w)]=cut;

}

} 

}

for(int j=1;j<100005;j++){

if(g[j]>0) ans++;

}

cout<<ans;

return 0;

}