0 mod n Sum Subset Problem
Given a set of numbers {a1-an}, what is the best way to come up with a nonempty subset such that the sum of its elements is 0 mod n, where n is the size of the original set?
目錄
思路
令Si = a0 + a1 + ... + ai，考慮數列[S0 % n, S1 % n, ..., Sn % n]，根據鴿籠原理，必定其中有一個Si是0 mod n，或是任兩個Si, Sj同屬k mod n。
所以mod n的情況下，必定存在subarray使得sum(subarray) = 0 mod n。
Si = 0 mod n的情況，Si就是要找的subset。
Si和Sj同屬k mod n的情況，Sj - Si就是要找的subset。
心得：滿有趣的性質，所有的subarray都可以用Si - Sj組出來