30 lines
693 B
C++
30 lines
693 B
C++
// lanqiao 1447 砝码称重(搜索)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e2 + 10;
|
|
int n, w[N], vis[N];
|
|
set<int> s;
|
|
void dfs(int sum, int dep){
|
|
if(dep == n + 2) return;
|
|
if(dep != 1) s.insert(sum);
|
|
for(int i = 1; i <= n; i++){
|
|
if(!vis[i]){
|
|
vis[i] = 1;
|
|
dfs(sum + w[i], dep + 1); // 砝码放在一边
|
|
dfs(abs(sum - w[i]), dep + 1); // 砝码放在另一边
|
|
vis[i] = 0; // 回溯状态重置
|
|
}
|
|
}
|
|
}
|
|
int main(){
|
|
cin >> n;
|
|
for(int i = 1; i <= n; i++) cin >> w[i];
|
|
dfs(0, 1);
|
|
if(s.count(0)) s.erase(0);
|
|
cout << s.size() << endl;
|
|
return 0;
|
|
}
|
|
/* test samples -> 10
|
|
3
|
|
1 4 6
|
|
*/ |