Can I Win — Solution

Problem

Two players take turns picking numbers from 1 to maxChoosableInteger. Each number can only be chosen once. A running total accumulates with every pick, and the player who causes it to reach or surpass desiredTotal wins. Given that both players play optimally, can the first player guarantee a win?

• Input: maxChoosableInteger = 10, desiredTotal = 11
• Output: false
• Explanation: For any number n the first player picks, the second player picks (11 − n), which is unused and immediately reaches 11.

Counter-example: maxChoosableInteger = 10, desiredTotal = 1 → true, because the first player simply picks 1 on their first turn.

Intuition

The game state is completely described by which numbers have already been chosen — once you know that set you know whose turn it is and exactly how much more is needed. Since at most 20 numbers are available, the entire set fits in a single integer bitmask, giving at most 2²⁰ unique states to explore. For each state the current player wins if any unchosen number either hits the target outright or hands the opponent a provably losing position.

Solution — Bitmask Memoization

Check two short-circuit conditions first: if desiredTotal ≤ 0 the first player wins without picking anything; if the total of all available numbers still falls short of desiredTotal nobody can ever win. For each remaining state, try every unchosen number and pick the first one that either wins immediately or puts the opponent in a losing game.

1. Return True if desiredTotal ≤ 0 (target already met before any pick).
2. Compute sum 1 + 2 + … + maxChoosableInteger; return False if it is less than desiredTotal.
3. Define a recursive helper with used_mask (which numbers are taken) and remaining (how much more is needed).
4. For each number not yet in used_mask: if it meets or exceeds remaining, the current player wins immediately.
5. Otherwise recurse with that number added to the mask; if the opponent loses from that state, the current player wins.
6. Cache the result for each used_mask so each of the 2^n states is computed only once.

1from functools import lru_cache
2
3def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
4    if desiredTotal <= 0:
5        return True
6    total_available = maxChoosableInteger * (maxChoosableInteger + 1) // 2
7    if total_available < desiredTotal:
8        return False
9
10    @lru_cache(maxsize=None)
11    def can_current_player_win(used_mask: int, remaining: int) -> bool:
12        for num in range(1, maxChoosableInteger + 1):
13            if used_mask & (1 << (num - 1)):
14                continue  # num was already chosen in a previous turn
15            if num >= remaining:
16                return True  # picking num reaches or passes desiredTotal
17            # picking num leaves the opponent in a losing position
18            if not can_current_player_win(used_mask | (1 << (num - 1)), remaining - num):
19                return True
20        return False  # every available move hands the win to the opponent
21
22    return can_current_player_win(0, desiredTotal)

Time: O(2^n × n) where n = maxChoosableInteger — there are 2^n unique bitmask states and each explores at most n choices.
Space: O(2^n) — the memo table stores one boolean per bitmask state.

Complexity Summary

Common Mistakes

• Missing the total-sum short-circuit: if the sum 1 + 2 + … + n is still below desiredTotal, no sequence of picks can ever reach the target — return False without searching. Omitting this causes TLE on inputs like maxChoosableInteger = 20, desiredTotal = 300.
• Using > instead of >= for the win condition: if remaining is 5 and you pick 5, the total hits the target exactly and you win. The correct boundary is num >= remaining, not num > remaining.
• Caching on remaining instead of usedMask: two different bitmasks can yield the same remaining value (e.g., picking {1, 3} and picking {4} both subtract 4 from the running total), but the available numbers differ, so their outcomes differ. The memo key must be usedMask.
• Off-by-one in the bit shift: writing 1 << num places number 1 at bit 1 and leaves bit 0 unused, while 1 << (num - 1) places number 1 at bit 0. Both are internally consistent, but mixing the two forms in the same function silently produces wrong bitmask comparisons.
• Not handling desiredTotal ≤ 0 as an immediate win: the problem allows desiredTotal = 0, where the running total already meets the target before the first pick, so the first player wins without making any move.

Related Problems

• target-sum — memoized DFS over a choice state that encodes which items have been assigned, with the same "current sum derivable from the mask" structure
• partition-equal-subset-sum — subset DP where the reachable sums form a bitmask over the target space
• subsets — directly enumerates all 2^n bitmask states to build every possible subset of a number set
• n-queens — backtracking that uses column and diagonal bitmasks to encode which positions are under attack
• word-break — memoized recursion over a shrinking state (remaining string) with the same "cache the sub-problem result" structure