Can I Win

Master this topic with zero to advance depth.

Can I Win

Two players take turns choosing integers from 1 to maxChoosableInteger without reuse. The first to reach desiredTotal wins. Return true if the first player can force a win.

Medium

Examples

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false

Approach 1

Level I: Recursive Minimax (No Memoization)

Intuition

Explore all possible sequences of choosing numbers. A player wins if they can pick a number that reaches the total, or if there is a number they can pick such that the other player cannot win from the resulting state.

Thought Process

Try choosing each available number $i \in [1, maxChoosableInteger]$ .
If $i \geq currentRemainder$ , you win.
Otherwise, if the other player cannot win from the state (remainder - $i$ , used numbers), you win.
If no such $i$ exists, you lose.

Pattern: Game Theory Recursion

⏱ O(M!) - Where $M$ is `maxChoosableInteger` (all permutations).💾 O(M) - Recursion depth.

java

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        return canWin(desiredTotal, new boolean[maxChoosableInteger + 1]);
    }
    
    private boolean canWin(int remainder, boolean[] used) {
        for (int i = 1; i < used.length; i++) {
            if (!used[i]) {
                if (i >= remainder) return true;
                used[i] = true;
                if (!canWin(remainder - i, used)) {
                    used[i] = false;
                    return true;
                }
                used[i] = false;
            }
        }
        return false;
    }
}

Approach 2

Level II: Recursion with Bitmask only

Intuition

Represent the state of used numbers with a 20-bit integer mask. This is more efficient for passing state through recursion but still suffers from exponential growth without memoization.

⏱ $O(2^M \cdot M)$ (without cache hit logic)💾 $O(M)$

java

class Solution {
    public boolean canIWin(int max, int total) {
        if (total <= 0) return true;
        if (max * (max + 1) / 2 < total) return false;
        return solve(total, 0, max);
    }
    private boolean solve(int rem, int mask, int max) {
        for (int i = 1; i <= max; i++) {
            if (((mask >> (i - 1)) & 1) == 0) {
                if (i >= rem || !solve(rem - i, mask | (1 << (i - 1)), max)) return true;
            }
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Bitmask DP / Memoization)

Intuition

The state of the game is uniquely determined by which integers have been used. Since maxChoosableInteger is at most 20, we can use a bitmask of length 20 to represent the set of used numbers. Memoizing the results of these masks drastically reduces the number of computations.

Thought Process

Use an integer mask where the $i$ -th bit is 1 if number $i$ is used.
Store result of canWin(mask) in a hash map or array.
Base cases: desiredTotal <= 0 or sum check.

Pattern: State Compression DP

⏱ O(2^M \cdot M) - $2^M$ possible states, each state takes $O(M)$ to compute transitions.💾 O(2^M) - To store the memoization table.

java

import java.util.*;

public class Solution {
    Map<Integer, Boolean> memo = new HashMap<>();
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        return solve(maxChoosableInteger, desiredTotal, 0);
    }
    
    private boolean solve(int max, int rem, int mask) {
        if (memo.containsKey(mask)) return memo.get(mask);
        for (int i = 1; i <= max; i++) {
            int curr = (1 << (i - 1));
            if ((mask & curr) == 0) {
                if (i >= rem || !solve(max, rem - i, mask | curr)) {
                    memo.put(mask, true);
                    return true;
                }
            }
        }
        memo.put(mask, false);
        return false;
    }
}

← Previous QuestionReverse Pairs

Next Question →Maximum AND Sum of Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.