Can I Win

medium math dp bitmask memoization game theory

Problem

Two players take turns picking integers from 1..maxChoosableInteger (without reuse). The first player to make the running sum reach or exceed desiredTotal wins. Assuming both players play optimally, return true if the first player can force a win.

InputmaxChoosableInteger = 10, desiredTotal = 11

Outputfalse

No matter which number 1..10 Player 1 picks, Player 2 can finish to ≥ 11.

maxChoosable

desiredTotal

def can_i_win(max_choosable, desired_total):
    if max_choosable * (max_choosable + 1) // 2 < desired_total: return False
    memo = {}
    def dfs(used, remaining):
        if used in memo: return memo[used]
        for i in range(1, max_choosable + 1):
            bit = 1 << (i - 1)
            if used & bit: continue
            if i >= remaining or not dfs(used | bit, remaining - i):
                memo[used] = True
                return True
        memo[used] = False
        return False
    return dfs(0, desired_total)

function canIWin(maxChoosable, desiredTotal) {
  if (maxChoosable * (maxChoosable + 1) / 2 < desiredTotal) return false;
  const memo = new Map();
  function dfs(used, remaining) {
    if (memo.has(used)) return memo.get(used);
    for (let i = 1; i <= maxChoosable; i++) {
      const bit = 1 << (i - 1);
      if (used & bit) continue;
      if (i >= remaining || !dfs(used | bit, remaining - i)) {
        memo.set(used, true); return true;
      }
    }
    memo.set(used, false); return false;
  }
  return dfs(0, desiredTotal);
}

class Solution {
    Map<Integer, Boolean> memo = new HashMap<>();
    int max;
    public boolean canIWin(int maxChoosable, int desiredTotal) {
        if (maxChoosable * (maxChoosable + 1) / 2 < desiredTotal) return false;
        max = maxChoosable;
        return dfs(0, desiredTotal);
    }
    boolean dfs(int used, int remaining) {
        if (memo.containsKey(used)) return memo.get(used);
        for (int i = 1; i <= max; i++) {
            int bit = 1 << (i - 1);
            if ((used & bit) != 0) continue;
            if (i >= remaining || !dfs(used | bit, remaining - i)) {
                memo.put(used, true); return true;
            }
        }
        memo.put(used, false); return false;
    }
}

class Solution {
    unordered_map<int, bool> memo;
    int M;
public:
    bool canIWin(int maxChoosable, int desiredTotal) {
        if (maxChoosable * (maxChoosable + 1) / 2 < desiredTotal) return false;
        M = maxChoosable;
        return dfs(0, desiredTotal);
    }
    bool dfs(int used, int remaining) {
        if (memo.count(used)) return memo[used];
        for (int i = 1; i <= M; i++) {
            int bit = 1 << (i - 1);
            if (used & bit) continue;
            if (i >= remaining || !dfs(used | bit, remaining - i)) {
                memo[used] = true; return true;
            }
        }
        memo[used] = false; return false;
    }
};

Explanation

This is a turn-based game, and the core idea is "I win if I have any move that leaves my opponent in a losing position." We explore the game tree with recursion and cache results so we never re-solve the same situation twice.

First a quick shortcut: if the sum of all numbers 1..max is still less than desiredTotal, nobody can ever reach the target, so we return False immediately.

The set of already-picked numbers is stored as a bitmask used — bit i-1 means number i is taken. For the current player we loop over every unused number i. If picking i reaches the target (i >= remaining) we win now; otherwise we recurse with dfs(used | bit, remaining - i). If that call returns False (the opponent loses), then this pick is a winning move.

If no pick leads to an opponent loss, the current player loses from this state. We store every result in memo[used] so repeated states are answered instantly.

Example: max = 10, desired = 11. Whatever number Player 1 takes, Player 2 can always add enough to reach 11, so Player 1 has no winning move and the answer is False.

Time: O(2^M · M) with memoization Space: O(2^M)