Google VO Interview Problem: Count the Number of Winning State Combinations

Imagine that each state is assigned a number of votes as follows:

Alabama = 9
Alaska = 3
Arizona = 11
Arkansas = 6
...
Wyoming = 3

For the purpose of this question, assume that all states are winner takes all. The winner of a state gets all the votes for that state.

To be elected, a candidate must win more than total_votes / 2. The candidate from Party 1 is running against the candidate from Party 2. How many different combinations of states won by Party 1 are there that will elect the Party 1 candidate?

For example, if Party 1 wins every state, the Party 1 candidate wins. If they win every state but lose Alabama, the candidate still wins.

Another example with three states:

StateA = 3
StateB = 4
StateC = 8

If Party 1 wins every state, their candidate will get elected. If they win StateA and StateC, their candidate will still get elected.

If they win StateA and StateB but lose StateC, their candidate will not get elected.

Total Combinations: 4

{StateA, StateB, StateC} = 15; {StateA, StateC} = 11; {StateB, StateC} = 12; {StateC} = 8. All these combinations are majority.

This problem asks for the number of subsets of states whose total votes exceed half of the overall vote count, since each state is winner-takes-all. The key is to treat every state as a binary choice and count only those combinations that reach a majority. A brute-force enumeration of all subsets is exponential, so the natural approaches are backtracking, memoized recursion, or dynamic programming for subset counting. The important detail is that we are counting distinct winning state sets, not permutations of the same states.