Skip to content

Electoral Tie Analysis

Level: L3-L5 Topics: Dynamic Programming, Subset Sum, Backtracking

Problem Statement

There are N states in an election, each worth a certain number of electoral points. Two candidates, A and B, are competing. Each state goes to exactly one candidate. Determine:

  1. Is it possible for the election to result in a tie (both candidates receive exactly half of the total electoral points)?
  2. If a tie is possible, which states must candidate A win in every tie scenario?

Background & Constraints

  • Each state has a positive integer number of electoral points.
  • The total electoral points across all states is T. A tie is possible only if T is even.
  • This is essentially a subset sum problem: can you find a subset of states whose electoral points sum to exactly T/2?
  • N can be up to a few hundred states.
  • Electoral point values can range from 1 to several hundred.

Examples

Example 1 — tie possible, no must-win state:

States: [3, 5, 8, 4, 10]
Total = 30, Half = 15

Tie is possible. Two distinct subsets sum to 15:
  {5, 10}        → A wins states with points 5, 10; B wins {3, 8, 4}
  {3, 8, 4}      → A wins states with points 3, 8, 4; B wins {5, 10}

No single state must be won by A: for every state, there is a tie
configuration that excludes it.

Example 1b — tie impossible:

States: [3, 5, 8, 10, 14]
Total = 40, Half = 20

No subset of these values sums to 20 (verifiable by enumerating all 2^5
subsets), so a tie is not achievable even though Total is even.

Example 2:

States: [6, 6, 4, 4]
Total = 20, Half = 10

Tie configurations: {6, 4} and {6, 4} (using different 6s and 4s)
- {state1(6), state3(4)} = 10
- {state1(6), state4(4)} = 10
- {state2(6), state3(4)} = 10
- {state2(6), state4(4)} = 10

No single state must be won by A in every configuration.

Hints & Common Pitfalls

  • Start with the basics: Check if the total is even. If T is odd, a tie is impossible.
  • Subset sum via DP: Use a boolean DP array where dp[s] = true if a subset summing to s exists. Build this up by iterating through states.
  • Finding "must-win" states: For each state with value v, check if a tie is still achievable without it. If removing a state makes T/2 unreachable (i.e., no subset of the remaining states sums to T/2 - v or the state must be included), then A must win that state.
  • Common mistake: Confusing "can be in a tie" with "must be in every tie." A state must be won by A only if every subset summing to T/2 includes it.
  • Runtime: The standard subset sum DP runs in O(N * T) time. This is pseudo-polynomial.

Follow-Up Questions

  1. What is the runtime of your subset sum solution? Is it polynomial?
  2. What if two states can have the same number of electoral points? Does your approach handle duplicates correctly?
  3. Can you improve the space complexity of your DP from O(T) to something better?
  4. How would you enumerate all possible tie configurations rather than just determining if one exists?
  5. What if the election has three candidates instead of two? How does the problem change?