HDU 4277 USACO ORZ

 1 #include <cstdio>
 2 #include <map>
 3 #include <iostream>
 4 using namespace std;
 5 struct node{
 6     int a,b;
 7     bool operator < (const node &aa) const
 8     {
 9         if(a!=aa.a) return a<aa.a;
10         else return b<aa.b;
11     }
12 };
13 map<node,bool> m;
14 int n,ans,sum;
15 int arr[20];
16 node nd;
17 void dfs(int cur,int a,int b)
18 {
19     int c=sum-a-b;
20     if(a>c||b>c||a>sum/3) return ;
21     if(cur==n)
22     {
23         if(a+b>c&&a+c>b&&b+c>a)
24         {
25             if(a>b) {int t=a;a=b;b=t;}
26             nd.a=a;nd.b=b;
27             if(!m.count(nd))
28             {
29                 m[nd]=1;
30                 ans++;
31             }
32         }
33         return;
34     }
35     dfs(cur+1,a+arr[cur],b);
36     dfs(cur+1,a,b+arr[cur]);
37     dfs(cur+1,a,b);
38 }
39 int main()
40 {
41     int t;
42     scanf("%d",&t);
43     while(t--)
44     {
45         scanf("%d",&n);
46         ans=0;sum=0;m.clear();
47         for(int i=0;i<n;i++) {scanf("%d",arr+i);sum+=arr[i];}
48         dfs(0,0,0);
49         printf("%d\n",ans);
50     }
51 }