Subsequence that Sums Up to Half the Total Sum

[TCAZN]

Hi all,

I was just looking at the U.S. electoral map, and I was wondering if there could possibly be a tie in presidential elections (the answer is probably no). I tried to think of an efficient algorithm to answer this question, but due to my limited intelligence and imagination, all I could think of is the brute force method. I guess in this particular problem, efficiency probably does not matter since the number of states definitely doesn't follow any kind of Moore's Law.

Anyways, I was just wondering if anyone knows an efficient algorithm for the following problem:

Given a finite sequence $$a_1, a_2, \dots a_n,$$ determine whether there is a sub-sequence $$a_{i_1}, a_{i_2}, \dots a_{i_k}$$ such that $$\sum_{j=1}^{k} a_{i_j} = \frac{1}{2} \sum_{j=1}^{n}a_j$$.

 

[willem2]

Google for "knapsack problem"

In this case, there are 2^51 combinations of states and only 500 or so possible values,
so it's almost certain some combination has half the votes. (unless the total number of votes is odd)
Just select states at random with a coin flip and you'll get it within a few thousand tries.

 

[micromass]

According to the New York Times’ FiveThirtyEight blog, one possible scenario to give each candidate 269 electoral votes would be if President Obama wins the following:

Washington, D.C.
California
Oregon
Washington
Hawaii
New Mexico
Minnesota
Michigan
Illinois
Wisconsin
Ohio
Pennsylvania
Maryland
Delaware
New Jersey
New York
Connecticut
Massachusetts
Rhode Island
New Hampshire
Vermont
Maine

Under that scenario, Gov. Romney would win all other states, including battleground states like Florida, Iowa, Virginia, Colorado and Nevada. The FiveThirtyEight blog pegs the chance of a tie occurring at 1.3%.

Source: http://foxnewsinsider.com/2012/10/24/what-happens-if-the-presidential-election-ends-in-a-tie/

 

[Edgardo]

Look up the partition problem. It seems that it can be solved with dynamic programming.