像方案数，种类数啥的一般都是dp，转移方程想不出，那就用暴搜，刚才自己用暴搜做，结果全错了，原因是在出口处的处理上，实际对于每次搜索，用一个bool数组去记录重量状态即可，最后遍历所有数，标记过的计数
`
`
#include<bits/stdc++.h>
using namespace std;
int n,a[105],ans;
bool st[100005];
void dfs(int x,int y,int u)
{
if(u==n+1)return;
st[abs(x-y)]=1;
dfs(x+a[u],y,u+1);
dfs(x,y+a[u],u+1);
dfs(x,y,u+1);
}
int main()
{
cin>>n;//天平有两边
for(int i=0;i<n;i++)cin>>a[i];
//单独一边 共Cni[1,n]求和
//分别两边
dfs(0,0,0);
for(int i=1;i<=100005;i++)
if(st[i])ans++;
cout<<ans;
return 0;
}
0 回复
0 转发
2 喜欢
0 阅读
