#464

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Can I Win

Determine if the first player can guarantee a win in a turn-based number selection game using state transition dynamic programming.

math dynamic programming bit manipulation memoization game theory

Problem Statement

Two players play a number selection game starting with a total of 0. Each turn, a player chooses any integer from 1 up to maxChoosableInteger that has not been previously chosen. The running total increases by the chosen number. The player whose move causes the total to reach or exceed desiredTotal wins. Determine if the first player can guarantee a win if both players play optimally.

The game can be thought of as drawing numbers from a common pool without replacement. For instance, if maxChoosableInteger = 15 and desiredTotal = 100, players alternate choosing unused numbers to reach or surpass 100. Your task is to implement a function that returns true if the first player has a forced win using a strategy based on state transitions and memoized exploration of all possible remaining numbers.

Examples

Example 1

Input: maxChoosableInteger = 10, desiredTotal = 11

Output: false

No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.

Example 2

Input: maxChoosableInteger = 10, desiredTotal = 0

Output: true

Example details omitted.

Example 3

Input: maxChoosableInteger = 10, desiredTotal = 1

Output: true

Example details omitted.

Constraints

1 <= maxChoosableInteger <= 20
0 <= desiredTotal <= 300

Solution Approach

Use Bitmasking to Track Choices

Represent the set of used integers with a single integer bitmask where the i-th bit indicates if number i+1 is taken. This allows fast state lookup and avoids revisiting identical game states, which is crucial for the exponential number of combinations in the game.

Recursive DFS with Memoization

Recursively simulate each player's turn, trying all available numbers. Memoize the results for each bitmask state so repeated subproblems are not recomputed. A state returns true if the current player can pick a number that guarantees a win, otherwise false.

Handle Edge Cases Efficiently

Check if the desiredTotal is zero or smaller than the maximum choosable integer to immediately return true. Also, if the sum of all numbers from 1 to maxChoosableInteger is less than desiredTotal, return false as a win is impossible. These checks prevent unnecessary recursion and early terminate trivial scenarios.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(2^N * N) where N is maxChoosableInteger, as each state can have N choices and there are 2^N possible bitmask states. Space complexity is O(2^N) for memoization of all bitmask states.

What Interviewers Usually Probe

Watch for exponential state space and propose memoization with bitmasking.
Ask if the player can immediately determine a win based on total sum constraints.
Clarify turn order and enforce choosing only unused numbers to avoid incorrect DP states.

Common Pitfalls or Variants

Common pitfalls

Failing to represent used numbers properly, leading to revisiting the same states multiple times.
Ignoring the case where desiredTotal is zero or negative and returning incorrect output.
Not checking if the total sum of all numbers is less than desiredTotal, causing unnecessary computation.

Follow-up variants

Modify the range of numbers or desired total and observe how the DP states scale with larger bitmasks.
Allow repeated picks of numbers to analyze the change in state transition logic.
Consider different winning thresholds for multi-player versions and extend the bitmask DP to more players.

FAQ

What is the main strategy to solve Can I Win efficiently?

Use recursive state transition dynamic programming combined with bitmasking and memoization to evaluate all possible number selections.

Why is bitmasking important in this problem?

Bitmasking compactly represents which numbers have been used, allowing fast lookup and avoiding recomputation of identical game states.

Can this approach handle the maximum constraints quickly?

Yes, memoization with bitmasking keeps the recursion feasible for maxChoosableInteger up to 20, as only valid states are evaluated once.

What edge cases should be considered for Can I Win?

Edge cases include desiredTotal <= 0, the sum of all numbers less than desiredTotal, and maxChoosableInteger being very small.

Is the first player always guaranteed a win if they pick optimally?

No, the first player can only guarantee a win if a recursive check of all possible moves shows at least one path that forces victory.

terminal

Solution

Solution 1: State Compression + Memoization

First, we check if the sum of all selectable integers is less than the target value. If so, it means that we cannot win no matter what, so we directly return `false`.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        @cache
        def dfs(mask: int, s: int) -> bool:
            for i in range(1, maxChoosableInteger + 1):
                if mask >> i & 1 ^ 1:
                    if s + i >= desiredTotal or not dfs(mask | 1 << i, s + i):
                        return True
            return False

        if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:
            return False
        return dfs(0, 0)

Continue Practicing

#638 shopping offers #691 stickers to spell word #698 partition to k equal sum subsets