Course4all

Can I Win

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

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

  1. Try choosing each available number i∈[1,maxChoosableInteger]i \in [1, maxChoosableInteger].
  2. If i≥currentRemainderi \geq currentRemainder, you win.
  3. Otherwise, if the other player cannot win from the state (remainder - ii, used numbers), you win.
  4. If no such ii 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

  1. Use an integer mask where the ii-th bit is 1 if number ii is used.
  2. Store result of canWin(mask) in a hash map or array.
  3. 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionReverse Pairs
Next Question →Maximum AND Sum of Array