一個(gè)經(jīng)典的問(wèn)題：給定n個(gè)數(shù)，求其中的任意一個(gè)子集滿足集合中的每個(gè)元素值加和正好是n的倍數(shù)。剛開(kāi)始怎么也沒(méi)有思路，因?yàn)閚很大，直接搜索顯然是不行的。后來(lái)在組合數(shù)學(xué)書(shū)上找到了這個(gè)例題（暈，之前白看了，居然把這個(gè)經(jīng)典的題目都給忘了），是抽屜原理的典型應(yīng)用。
　　假定n個(gè)數(shù)為a1，a2，...，an，前n項(xiàng)和分別是S1、S2、...、Sn，那么如果有一個(gè)Si模n是0，就是答案，否則，n個(gè)數(shù)模n的余數(shù)只能在1到n - 1之間，把余數(shù)作為抽屜，顯然n個(gè)數(shù)放到n - 1個(gè)抽屜里面，肯定有兩個(gè)數(shù)余數(shù)相等，這樣取它們的差就得到了結(jié)果，算法復(fù)雜度是O(n)的。
　　抽屜原理的應(yīng)用都十分巧妙。還有一個(gè)例子，一個(gè)屋子里面有n個(gè)人，他們的最大年齡不超過(guò)k歲，問(wèn)是否肯定存在2組人（兩組沒(méi)有重復(fù)的人），使得這兩組人的年齡和相等。n個(gè)人的組合一共有2 ^ n種方法，注意到最大情況n的人的年齡和是n * k，這樣如果2 ^ n > n * k，根據(jù)抽屜原理，一定存在兩種組合他們的年齡和相等，而且沒(méi)有重復(fù)的人（如果重復(fù)，把那個(gè)人刪去就行了）。所以O(shè)(1)的時(shí)間就判斷出了結(jié)果。
　　不過(guò)在最開(kāi)始做題目（PKU 2356）的時(shí)候，雖然代碼很短，但是錯(cuò)了好多次。首先是數(shù)組開(kāi)小了，然后發(fā)現(xiàn)輸出的時(shí)候題目要求的是輸出數(shù)但是我給輸出下標(biāo)了。最后的問(wèn)題出在一個(gè)很關(guān)鍵的地方，在取模為零的時(shí)候，我本應(yīng)該直接就記錄產(chǎn)生了解，但是我以為取模為零的時(shí)候下次肯定會(huì)產(chǎn)生重復(fù)的標(biāo)記，就沒(méi)有特殊處理。其實(shí)如果第一個(gè)數(shù)取模就是0的話，就有可能后面不產(chǎn)生重復(fù)的標(biāo)記，這樣我的程序就錯(cuò)了，還有就是最后一個(gè)是取模為零的時(shí)候也會(huì)出問(wèn)題。想了很久才想到這個(gè)問(wèn)題，改正之后終于過(guò)了。以后寫(xiě)程序要仔細(xì)，不能想當(dāng)然啊。
附PKU 2356代碼：