描述

一个整数集合，我们定义“兄弟数”如下：集合中的某一个数可以表示成集合内其他数之和，则称这几个数为“兄弟数”。

如集合{1,3,4,6}中只有一组1+3=4满足以上定义，所以这个集合只有一组“兄弟数”。

再比如集合{1,3,4,8}中有1+3=4 和 1+3+4=8 这两组数满足，所以这个集合有两组兄弟数；

现在给定一个整数集合，请编写程序，求出这个集合中所有“兄弟数”的组数。程序需要处理多组输入数据。

输入

第一行为正整数M（1≤M≤10）M（1≤M≤10）M（1≤M≤10），表示整数集合的个数（数据的组数）；

接下来M行，每行第一个数K（1≤K≤30）K（1≤K≤30）K（1≤K≤30）是集合元素的个数，接下来该行有K个不同的整数x（1≤x≤1000）x（1≤x≤1000）x（1≤x≤1000）。一行内的整数用空格隔开。

输出

共M行，每行一个整数，表示每组集合“兄弟数”的组数。

输入样例 1

3 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6

输出样例1

1 0 7

#include<bits/stdc++.h>
using namespace std;
int m,n,r,cnt=0;
int x[35],a[35];
int t[1000005];
void temp(){
	int sum=0;
	for(int i=1;i<=r;i++){
		sum+=x[a[i]];
	}
	t[sum]++;
}
void dfs(int k){
    int i;
    if(k>r){
        temp();
        return;
    }
    for(i=a[k-1]+1;i<=n;i++){
        a[k]=i;
        dfs(k+1);
    }
}  
int main(){   
    cin>>m;
    while(m--){
    	cin>>n;
    	int cnt=0;
    	memset(t,0,sizeof(t));
    	for(int i=1;i<=n;i++){
    		cin>>x[i];
		}
		for(int i=2;i<n;i++){
			r=i;
			dfs(1);
		}
		for(int i=1;i<=n;i++){
			cnt+=t[x[i]];
		}
		cout<<cnt<<endl;
	}
    return 0;  
}  

TLE

好像搜爆了...... 求优化 超时数据：

输入：
8
25 684 752 694 959 242 774 109 658 615 594 648 128 224 407 443 982 516 167 354 388 680 229 380 72 267 
13 557 725 804 281 94 605 273 969 309 490 378 635 134 
5 48 159 240 70 357 
4 849 853 632 117 
18 63 134 337 958 831 422 689 581 846 699 841 915 333 369 129 453 981 56 
25 704 621 307 85 266 793 857 295 145 482 227 468 608 559 935 416 195 343 911 758 123 245 52 810 50 
24 779 269 457 188 129 644 716 742 36 46 631 237 975 34 268 5 243 283 753 387 608 196 292 892 
12 474 501 521 433 862 370 911 130 64 446 259 573 
输出：
24
0
0
0
6
40
98
0