LeetCode 464: Can I Win

Problem Restatement

We are given two integers:

maxChoosableInteger
desiredTotal

There are numbers from 1 to maxChoosableInteger.

Two players take turns choosing one unused number.

Each chosen number is added to a running total.

The player who makes the running total reach or exceed desiredTotal wins.

Both players play optimally.

We need to return whether the first player can force a win. The official problem asks whether the first player can force a win given maxChoosableInteger and desiredTotal.

Input and Output

Function shape:

def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
    ...

Examples

Example 1:

maxChoosableInteger = 10
desiredTotal = 11

The first player cannot force a win.

If the first player chooses any number x, the second player can choose 11 - x when it is available and reach 11.

Answer:

False

Example 2:

maxChoosableInteger = 10
desiredTotal = 0

The target has already been reached before any move.

Answer:

True

Example 3:

maxChoosableInteger = 10
desiredTotal = 1

The first player chooses 1 immediately.

Answer:

True

First Thought: Try Every Game

A direct way is to simulate every possible game.

On the first move, the player can choose any number from 1 to maxChoosableInteger.

Then the second player can choose any remaining number.

Then the first player chooses again.

This forms a game tree.

At each state:

1. If some available number reaches the target, the current player wins.
2. Otherwise, the current player tries a move that makes the opponent lose.

This is the correct idea, but without memoization it repeats many states.

Problem With Plain Recursion

The same remaining numbers can be reached in different orders.

For example, choosing:

1 then 3

and choosing:

3 then 1

lead to the same set of used numbers.

The future game only depends on which numbers are used, not the order used to reach that state.

Without memoization, the recursion recomputes the same states many times.

Since maxChoosableInteger <= 20, we can represent the used numbers with a bitmask. This gives at most:

2^20

states.

Key Insight

A game state can be represented by the set of used numbers.

Use a bitmask:

mask

If bit i is 1, then number i has already been chosen.

For example:

mask = 0b1010

means numbers 1 and 3 are used if we map number i to bit i.

At each state, the recursive function returns:

True

if the current player can force a win from that state.

A move is winning if:

1. The chosen number reaches the target immediately.
2. Or after choosing it, the opponent is in a losing state.

Important Early Checks

First, if:

desiredTotal <= 0

then the first player wins immediately.

Second, compute the sum of all choosable numbers:

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

If:

total < desiredTotal

then even choosing all numbers cannot reach the target.

So the first player cannot win.

Algorithm

Define:

dfs(mask, remaining)

where:

The function returns whether the current player can force a win.

For each number x from 1 to maxChoosableInteger:

1. If x is already used, skip it.
2. If x >= remaining, the current player wins immediately.
3. Otherwise, choose x and recursively check the opponent’s state.
4. If the opponent cannot win, the current player can force a win.

If no move works, return False.

Memoize results by mask.

We can memoize only by mask because remaining is determined by the original desiredTotal minus the sum of numbers already used.

Correctness

At any turn, the current player wins immediately if they can choose an unused number at least as large as remaining.

If no immediate winning move exists, the current player needs to choose a number that leaves the opponent in a losing state.

The recursive function checks every legal unused number. For each choice, it asks whether the opponent can win from the resulting state.

If at least one choice makes the opponent lose, then the current player can force a win by choosing that number.

If every legal choice lets the opponent win, then no strategy can force a win for the current player.

The memoization stores the result for each used-number set. Since the future options depend only on which numbers remain, reusing this result is valid.

Therefore, dfs(0, desiredTotal) correctly returns whether the first player can force a win.

Complexity

Let:

m = maxChoosableInteger

Since m <= 20, this is feasible.

Implementation

from functools import cache

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

        total = maxChoosableInteger * (maxChoosableInteger + 1) // 2
        if total < desiredTotal:
            return False

        @cache
        def dfs(mask: int, remaining: int) -> bool:
            for x in range(1, maxChoosableInteger + 1):
                bit = 1 << x

                if mask & bit:
                    continue

                if x >= remaining:
                    return True

                if not dfs(mask | bit, remaining - x):
                    return True

            return False

        return dfs(0, desiredTotal)

Code Explanation

We first handle the immediate win case:

if desiredTotal <= 0:
    return True

Then we check whether reaching the target is possible at all:

total = maxChoosableInteger * (maxChoosableInteger + 1) // 2
if total < desiredTotal:
    return False

The recursive function:

dfs(mask, remaining)

answers whether the current player can win from the current state.

For each possible number:

for x in range(1, maxChoosableInteger + 1):

we compute its bit:

bit = 1 << x

If that bit is already set, the number was used:

if mask & bit:
    continue

If choosing x reaches the target, the current player wins:

if x >= remaining:
    return True

Otherwise, we move to the opponent’s state:

dfs(mask | bit, remaining - x)

If the opponent cannot win from there, the current player wins:

if not dfs(mask | bit, remaining - x):
    return True

If every choice fails:

return False

Testing

def run_tests():
    s = Solution()

    assert s.canIWin(10, 11) is False
    assert s.canIWin(10, 0) is True
    assert s.canIWin(10, 1) is True
    assert s.canIWin(10, 40) is False
    assert s.canIWin(5, 50) is False
    assert s.canIWin(5, 6) is False
    assert s.canIWin(5, 5) is True
    assert s.canIWin(20, 210) is False

    print("all tests passed")

run_tests()

Test meaning: