So I was thinking about the election and I was wondering if you had N numbers, what type of algorithm would best be able to tell you if a tie is possible? I know that the sum being divisible by an even number doesn't necessarily mean there is a way to tie. This was inspired by thinking of the up coming election. You can assume all numbers in N are positive and that there may be numbers repeated, think electoral college as an example.
This is the partition problem[1]. So to answer your question: the problem is NP-complete, but there are pseudo-polynomial time dynamic programming solutions (see the wikipedia entry for details).<p>[1]: <a href="http://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">http://en.wikipedia.org/wiki/Partition_problem</a>
Off the top of my head:<p><pre><code> 1. sum all the numbers
2. if the sum is odd, then return false
3. else determine if any set of numbers adds to half the sum
</code></pre>
To determine if any set of numbers adds to half the sum:<p><pre><code> 1. choose a number and add it to the set
2. if the sum of the set is less than the number, add another number to the set
3. else remove a number from the set
</code></pre>
which numbers to add and remove can be done via brute force, but there is probably a better way.