http://www.cnblogs.com/dongsheng/archive/2012/11/03/2752725.html
/*
抽屉原理，又叫鸽巢原理
题意：
给出N个数，问其中是否存在M个数使其满足M个数的和是N的倍数，如果有多组解，
随意输出一组即可。若不存在，输出 0。
题解：
首先必须声明的一点是本题是一定是有解的。原理根据抽屉原理：
因为有n个数，对n个数取余，如果余数中没有出现0，根据鸽巢原理，一定有两个数的余数相同，
如果余数出现0，自然就是n的倍数。也就是说，n个数中一定存在一些数的和是n的倍数。
本题的思路是从第一个数开始一次求得前 i（i <= N）项的和关于N的余数sum，并依次记录相应余数的存在状态，
如果sum == 0；则从第一项到第i项的和即满足题意。如果求得的 sum 在前边已经出现过，假设在第j（j
过相同的 sum 值，则从第 j+1 项到第i项的和一定满足题意。
//
//代码一：
#include
#include
#include
using namespace std;
const int MAX = 10001;
int mod[MAX], num[MAX];
int sum;
void print(int begin, int end)
{
printf("%d\n", end - begin + 1);
while(begin <= end)
printf("%d\n", num[begin++]);
}
int main()
{
int n;
bool flag = false;
int begin, end;
while(~scanf("%d", &n))
{
memset(mod, -1, sizeof(mod));
sum = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &num[i]);
if(flag)
continue;
sum = (sum + num[i]) % n;
if(sum == 0)
{
// print(1, i);
begin = 1;
end = i;
flag = true;
continue;
}
if(mod[sum] != -1)
{
// print(sum + 1, i);
begin = sum + 1;
end = i;
flag = true;
continue;
}
mod[sum] = i; //mod数组用来记录出现余数为sum时位置，即前i项和除以N余数为sum
}
print(begin, end);
}
return 0;
}
*/
//代码二：---COPY 用搜索做的
//不过他是直接从头一直向后延伸，从第一个数开始直到找到前x项的和满足解为止，感觉只能适应本题
//这种解肯定存在的情况，如果用在其他题中，这种贪心应该就不对了
#include
usingnamespacestd;
inta[10001], n, m;
booldfs(intsum,intk)
{
inti;
if(sum%n == 0 && sum >= n)
{
cout << m << endl;
returntrue;
}
for(i = k+1; i <= n; i++)
{
m++;
if(dfs(sum+a[i], i))
{
cout << a[i] << endl;
returntrue;
}
m--;
}
returnfalse;
}
intmain()
{
inti, j;
cin >> n;
for(i = 1; i <= n; i++)
cin >> a[i];
m=0;
if(!dfs(0,0))
cout << 0 << endl;
return0;
}
