Imagine that each state is assigned a number of votes as follows:
Alabama = 9
Alaska = 3
Arizona = 11
Arkansas = 6
...
Wyoming = 3For 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 = 8If 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.这题本质上是在统计“能让 Party 1 获得多数票的州集合有多少种”。每个州只有“赢”或“输”两种状态，且赢家通吃，因此问题可以转化为：从所有州中选出若干州，使它们的票数和严格大于总票数的一半。由于州的数量可能较多，直接枚举所有子集会指数爆炸，通常会用回溯、记忆化搜索或动态规划来统计满足条件的组合数。核心在于先求总票数，再围绕“达到多数线”的目标做子集计数，注意这里统计的是不同州组合，而不是排列顺序。
