Ask HN: With N numbers, determine if a tie is possible? 2 points by syberslidder 1865 days ago | hide | past | web | favorite | 2 comments 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).
 Off the top of my head:`````` 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 `````` To determine if any set of numbers adds to half the sum:`````` 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 `````` which numbers to add and remove can be done via brute force, but there is probably a better way.

Search: