Algorithm to find the minimum (additional) popular votes to win the electoral college So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election.
Assuming we are considering n states each with some different electoral votes. The candidate who has a majority receive all these votes from that state; and the one with the majority of electoral votes win the presidency. The number of electoral votes of a state is not necessarily proportional to its size of voters.
At a certain instance of vote counting, each candidate receives certain amounts of votes and there are still some uncounted in every states. I want to keep track of the minimum number of the remaining votes (regardless which state they are from) from these candidates to win the election until its secured.

So far the only algorithm in my head is to compute all the combinations of states to win the majority electoral votes, then weed out those which are not possible (the candidate won't win even he/she gains all the remaining votes). Compute the additional popular votes needed (win each of these states by exactly 1 vote) and then find_min among them.  But this would rather have redundant time complexity as it would take the same amount of time to compute no matter how many votes left...
Here's a hint (and a sketch).
I believe the problem is NP-hard and that it is equivalent to Subset Sum.
Reducing from Subset Sum:  Suppose your instance has sum $S$ and values $v_1, v_2, \dots, v_n$.
Create $n+1$ states, one with $S$ electorals that Party $A$ is guaranteed to win.  The remaining $n$ states is such that $i$ has $v_i$ electorals.  These cost Party $B$ $v_i$ to win.
Now, the optimum solution is $S$ which exists if and only if you have a yes instance for Subset Sum.