http://www.cnblogs.com/dongsheng/archive/2012/11/03/2752725.html
/*
抽屜原理损搬，又叫鴿巢原理
題意：
給出N個(gè)數(shù)煞肾，問其中是否存在M個(gè)數(shù)使其滿足M個(gè)數(shù)的和是N的倍數(shù)，如果有多組解，
隨意輸出一組即可。若不存在，輸出 0弹灭。
題解：
首先必須聲明的一點(diǎn)是本題是一定是有解的。原理根據(jù)抽屜原理：
因?yàn)橛衝個(gè)數(shù)揪垄，對n個(gè)數(shù)取余穷吮，如果余數(shù)中沒有出現(xiàn)0，根據(jù)鴿巢原理饥努，一定有兩個(gè)數(shù)的余數(shù)相同捡鱼，
如果余數(shù)出現(xiàn)0，自然就是n的倍數(shù)酷愧。也就是說驾诈，n個(gè)數(shù)中一定存在一些數(shù)的和是n的倍數(shù)缠诅。
本題的思路是從第一個(gè)數(shù)開始一次求得前 i（i <= N）項(xiàng)的和關(guān)于N的余數(shù)sum，并依次記錄相應(yīng)余數(shù)的存在狀態(tài)乍迄，
如果sum == 0管引；則從第一項(xiàng)到第i項(xiàng)的和即滿足題意。如果求得的 sum 在前邊已經(jīng)出現(xiàn)過闯两，假設(shè)在第j（j
過相同的 sum 值褥伴，則從第 j+1 項(xiàng)到第i項(xiàng)的和一定滿足題意。
//
//代碼一：
#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數(shù)組用來記錄出現(xiàn)余數(shù)為sum時(shí)位置生蚁，即前i項(xiàng)和除以N余數(shù)為sum
}
print(begin, end);
}
return 0;
}
*/
//代碼二：---COPY 用搜索做的
//不過他是直接從頭一直向后延伸噩翠，從第一個(gè)數(shù)開始直到找到前x項(xiàng)的和滿足解為止，感覺只能適應(yīng)本題
//這種解肯定存在的情況邦投，如果用在其他題中，這種貪心應(yīng)該就不對了
#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;
}
