LeetCode 464 - Can I Win

This problem describes a two-player turn-based game. Players take turns choosing a number from a shared pool of integers ranging from 1 to maxChoosableInteger. Once a number is chosen, it cannot be used again for the rest of the game.

leetcodemediummathdynamic-programmingbit-manipulationmemoizationgame-theorybitmask

LeetCode Problem 464

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Game Theory, Bitmask

Solution

LeetCode 464 - Can I Win

Problem Understanding

This problem describes a two-player turn-based game. Players take turns choosing a number from a shared pool of integers ranging from 1 to maxChoosableInteger. Once a number is chosen, it cannot be used again for the rest of the game.

Each chosen number is added to a running total. The player who causes the running total to become greater than or equal to desiredTotal wins immediately.

The task is to determine whether the first player can force a win if both players play optimally.

The input consists of two integers:

  • maxChoosableInteger defines the maximum selectable number, meaning the available numbers are 1 through maxChoosableInteger
  • desiredTotal defines the target sum needed to win

The output is a boolean:

  • true means the first player can guarantee victory
  • false means the second player can always prevent the first player from winning

The constraints are important:

  • maxChoosableInteger <= 20
  • desiredTotal <= 300

The small upper bound of 20 strongly suggests that bitmasking is feasible. Since there are at most 20 numbers, every game state can be represented using a 20-bit integer. This observation is critical for the optimal solution.

Several edge cases appear immediately:

If desiredTotal == 0, the first player already satisfies the condition before making a move, so the answer is automatically true.

If the sum of all available numbers is still smaller than desiredTotal, then nobody can ever reach the target. In that case, the first player cannot win.

The total sum of numbers from 1 to maxChoosableInteger is:

$1+2+\cdots+n=\frac{n(n+1)}{2}$

For this problem:

maxPossibleSum = maxChoosableInteger * (maxChoosableInteger + 1) / 2

If this value is less than desiredTotal, the answer must be false.

Another important challenge is repeated states. Different sequences of moves may produce the same set of remaining numbers. A naive recursive search would recompute the same game states repeatedly, causing exponential blowup.

Approaches

Brute Force Approach

A brute-force solution recursively simulates every possible game path.

At each turn, the current player tries every unused number. After choosing a number, the algorithm recursively checks whether the opponent can win from the resulting state.

The recursive logic works like this:

  • If choosing a number immediately reaches desiredTotal, the current player wins
  • Otherwise, recursively simulate the opponent's turn
  • If any move causes the opponent to lose, then the current player can force a win

This approach is logically correct because it exhaustively explores the game tree under optimal play assumptions.

However, the same states are recomputed many times. For example, the state where numbers {1, 3, 5} are already used can be reached through multiple move orders:

  • 1 -> 3 -> 5
  • 3 -> 1 -> 5
  • 5 -> 3 -> 1

Without caching, each state gets recalculated repeatedly, making the solution far too slow.

The worst-case branching factor is large, and the recursion tree grows factorially.

Optimal Approach, DFS + Memoization + Bitmasking

The key insight is that the game state is completely determined by which numbers have already been used.

The exact order of moves does not matter once we know the used numbers and the remaining target.

Because maxChoosableInteger <= 20, we can encode the used numbers inside a bitmask:

  • Bit i represents whether number i + 1 has been chosen
  • A 1 bit means the number is already used
  • A 0 bit means the number is still available

This allows each unique game state to be represented efficiently as an integer.

We then use depth-first search with memoization:

  • DFS explores all possible moves
  • Memoization stores whether a particular bitmask state is winning or losing

The recursive strategy becomes:

  • Try every available number
  • If choosing that number wins immediately, return true
  • Otherwise, recursively check the opponent's result
  • If the opponent loses in any branch, the current player wins

Because each state is computed once, the algorithm becomes feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Explores all move permutations without caching
Optimal O(2^n * n) O(2^n) Uses memoization and bitmask states

Algorithm Walkthrough

  1. Handle trivial winning conditions.

If desiredTotal <= 0, the first player already satisfies the target condition without making any move, so return true. 2. Check whether reaching the target is mathematically possible.

Compute the sum of all numbers from 1 to maxChoosableInteger.

totalSum = n * (n + 1) / 2

If totalSum < desiredTotal, no sequence of moves can ever reach the target, so return false. 3. Represent game states using a bitmask.

Use an integer where each bit indicates whether a number has already been chosen.

For example, if maxChoosableInteger = 5:

Bitmask Used Numbers
00000 none
00101 1 and 3
11111 all numbers
4. Define the recursive DFS function.

The DFS function receives:

  • usedMask, representing which numbers are already taken
  • remaining, representing how much more is needed to win

The function returns whether the current player can force a win from this state. 5. Try every available number.

For each number from 1 to maxChoosableInteger:

  • Skip it if already used
  • Otherwise, consider choosing it
  1. Check immediate winning moves.

If the chosen number is greater than or equal to remaining, the current player wins immediately. 7. Simulate the opponent.

Mark the chosen number as used and recursively evaluate the opponent's position.

If the recursive call returns false, that means the opponent loses from that state, so the current player can force a win. 8. Memoize the result.

Store the result for the current usedMask so future calls can reuse it instantly. 9. Return the final answer.

Start DFS from:

  • usedMask = 0
  • remaining = desiredTotal

Why it works

The algorithm relies on optimal play and recursive game-state evaluation.

A state is winning if there exists at least one move that forces the opponent into a losing state.

A state is losing if every possible move allows the opponent to eventually win.

Memoization guarantees that each unique state is solved exactly once, and bitmasking ensures compact state representation.

Python Solution

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= 0:
            return True

        total_sum = maxChoosableInteger * (maxChoosableInteger + 1) // 2

        if total_sum < desiredTotal:
            return False

        memo = {}

        def dfs(used_mask: int, remaining: int) -> bool:
            if used_mask in memo:
                return memo[used_mask]

            for number in range(1, maxChoosableInteger + 1):
                bit = 1 << (number - 1)

                if used_mask & bit:
                    continue

                if number >= remaining:
                    memo[used_mask] = True
                    return True

                next_mask = used_mask | bit

                opponent_can_win = dfs(next_mask, remaining - number)

                if not opponent_can_win:
                    memo[used_mask] = True
                    return True

            memo[used_mask] = False
            return False

        return dfs(0, desiredTotal)

The implementation begins with two important edge-case checks.

If desiredTotal <= 0, the first player trivially wins because the target has already been met.

Next, the algorithm computes the maximum possible sum using all numbers. If even that total cannot reach desiredTotal, winning is impossible.

The memo dictionary stores previously computed game states. The key is the bitmask representing used numbers, and the value indicates whether the current player can force a win from that state.

The recursive dfs function explores every available move.

For each candidate number:

  • A bit is computed using 1 << (number - 1)
  • If the bit is already set, the number has already been used
  • Otherwise, the move is evaluated

If choosing the number immediately satisfies the target, the function returns True.

Otherwise, the algorithm recursively evaluates the opponent's position after updating the bitmask and decreasing the remaining target.

If the opponent cannot win from that next state, then the current player has found a winning strategy.

If every possible move still allows the opponent to win, the current state is losing.

Go Solution

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	if desiredTotal <= 0 {
		return true
	}

	totalSum := maxChoosableInteger * (maxChoosableInteger + 1) / 2

	if totalSum < desiredTotal {
		return false
	}

	memo := make(map[int]bool)
	visited := make(map[int]bool)

	var dfs func(int, int) bool

	dfs = func(usedMask int, remaining int) bool {
		if visited[usedMask] {
			return memo[usedMask]
		}

		for number := 1; number <= maxChoosableInteger; number++ {
			bit := 1 << (number - 1)

			if usedMask&bit != 0 {
				continue
			}

			if number >= remaining {
				memo[usedMask] = true
				visited[usedMask] = true
				return true
			}

			nextMask := usedMask | bit

			opponentCanWin := dfs(nextMask, remaining-number)

			if !opponentCanWin {
				memo[usedMask] = true
				visited[usedMask] = true
				return true
			}
		}

		memo[usedMask] = false
		visited[usedMask] = true
		return false
	}

	return dfs(0, desiredTotal)
}

The Go implementation follows the same recursive strategy as the Python version.

One notable difference is memoization handling. Since Go maps return the zero value for missing keys, a separate visited map is used to distinguish between:

  • a state that has not been computed
  • a state that has been computed and evaluates to false

Bitmask operations work naturally with integers in Go, and the recursion structure remains almost identical to Python.

Worked Examples

Example 1

Input:
maxChoosableInteger = 10
desiredTotal = 11

The total available sum is:

1 + 2 + ... + 10 = 55

So reaching 11 is possible.

Initial state:

Variable Value
usedMask 0000000000
remaining 11

The first player tries all possible moves.

First player chooses 1

Variable Value
usedMask 0000000001
remaining 10

Now the second player can choose 10 immediately.

1 + 10 = 11

Second player wins.

First player chooses 2

Variable Value
usedMask 0000000010
remaining 9

Second player chooses 9 and wins immediately.

The same pattern continues:

First Move Second Winning Move
1 10
2 9
3 8
4 7
5 6

Every opening move has a direct counter.

Therefore, the first player cannot force a win.

Output: false

Example 2

Input:
maxChoosableInteger = 10
desiredTotal = 0

Since the target is already satisfied before any move:

Output: true

The algorithm returns immediately during the edge-case check.

Example 3

Input:
maxChoosableInteger = 10
desiredTotal = 1

Initial state:

Variable Value
usedMask 0000000000
remaining 1

The first player can choose 1.

Since:

1 >= remaining

the first player wins instantly.

Output: true

Complexity Analysis

Measure Complexity Explanation
Time O(2^n * n) There are at most 2^n bitmask states, and each state tries up to n numbers
Space O(2^n) Memoization stores results for each unique bitmask

The key observation is that the algorithm computes each bitmask state once.

For every state, the algorithm iterates through all possible numbers to determine valid moves. Since there are at most 2^20 states, the solution is efficient enough for the problem constraints.

Test Cases

solution = Solution()

assert solution.canIWin(10, 11) == False  # Provided example, first player loses
assert solution.canIWin(10, 0) == True    # Target already reached
assert solution.canIWin(10, 1) == True    # Immediate winning move

assert solution.canIWin(5, 50) == False   # Impossible to reach desiredTotal
assert solution.canIWin(20, 210) == False # Sum exactly equals 210, parity matters
assert solution.canIWin(20, 0) == True    # Zero target edge case

assert solution.canIWin(4, 6) == True     # First player can force win
assert solution.canIWin(4, 10) == False   # All numbers sum to target

assert solution.canIWin(1, 1) == True     # Single number immediate win
assert solution.canIWin(1, 2) == False    # Cannot reach target

assert solution.canIWin(2, 3) == False    # Second player always wins
assert solution.canIWin(3, 5) == True     # Recursive winning path

assert solution.canIWin(18, 79) == True   # Larger state-space test
assert solution.canIWin(20, 300) == False # Maximum desiredTotal stress case
Test Why
(10, 11) Validates classic losing configuration
(10, 0) Tests immediate success edge case
(10, 1) Tests immediate winning move
(5, 50) Verifies impossible target detection
(20, 210) Tests total sum exactly equal to target
(20, 0) Confirms zero-target handling
(4, 6) Validates recursive winning strategy
(4, 10) Tests parity and forced-loss behavior
(1, 1) Smallest valid winning input
(1, 2) Smallest impossible input
(2, 3) Simple forced-loss state
(3, 5) Small recursive game tree
(18, 79) Larger memoization scenario
(20, 300) Stress test near upper bounds

Edge Cases

One important edge case occurs when desiredTotal is zero or negative. In this scenario, the game is effectively already won before any moves occur. A naive implementation might incorrectly start recursion anyway. The solution handles this immediately with an early return.

Another critical edge case appears when the sum of all available numbers is still smaller than desiredTotal. Without checking this condition upfront, the recursion would explore many impossible states before eventually failing. The implementation prevents unnecessary computation by returning false immediately.

A more subtle edge case involves repeated states reached through different move orders. For example, choosing numbers {1, 3} leads to the same game state regardless of whether the order was 1 -> 3 or 3 -> 1. Without memoization, these states would be recomputed repeatedly, causing exponential slowdown. The bitmask representation ensures identical states map to the same memoized result.

Another tricky case occurs when a player can win immediately by selecting a number greater than or equal to the remaining target. If the implementation recurses before checking this condition, it may incorrectly continue exploring deeper states. The algorithm explicitly checks immediate-winning moves before recursion begins.