杭电acm 1557解决方法

杭电acm 1557
这道题该咋想啊~跪求思路~
------解决方案--------------------
如果LZ想研究这类题的算法请忽略这个帖子，
如果LZ单纯想过这道题就参考一下吧，虽然方法很水。
做法是每次选出一个数
DFS枚举所有不包括这个数的可能得到的和如果小于这个数的一半
加上选中那个数大于等于总和的一半结果就加1。
这里还加了个减枝枚举到的和如果和大于和的一半就不可能是结果了剪掉。
这题本意应该不是这么作，但是数据小测试数据也水就这么过去了。
218MS 248K水过

#include<iostream>

#include<cstdio>

using namespace std;


int vis[50];

int a[50], res, temp1, sum;

int n, T;

void dfs(int p, int q, int s)

{


	if(2 * q > sum)

		return;

	int i, temp;

	if(2 * q < sum && 2 * (q + a[p]) >= sum)

		res++;


	for(i = s; i < n; i++)

	{

		if(i != p && vis[i] == -1)

		{

			temp = q + a[i];

			vis[i] = 1;

			dfs(p, temp, i + 1);

			vis[i] = -1;

		}

	}

}

int main()

{	

	int i;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d", &n);

		sum = 0;

		for(i = 0; i < n; i++)

		{

			scanf("%d", &a[i]);

			sum += a[i];

			vis[i] = -1;

		}

		res = 0;

		dfs(0, 0, 0);

		printf("%d", res);

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

		{

			res = 0;

			dfs(i, 0, 0);

			printf(" %d", res);

		}


		printf("\n");

	}

	return 0;

}