Problem

In the “100 game” two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
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

1
2

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3

1
2

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

Constraints

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

Solution

Method 1 – Bitmask DP with Memoization

Intuition

We use bitmasking to represent which numbers have been picked. At each turn, the current player tries all available numbers. If picking any number leads to a state where the opponent cannot win, the current player can force a win. Memoization avoids recomputation.

Approach

  1. If the sum of all numbers is less than desiredTotal, return false (no one can win).
  2. If desiredTotal is 0, return true (first player wins by default).
  3. Use a recursive function with memoization:
  • The state is represented by a bitmask of used numbers.
  • For each unused number, try picking it:
    • If picking it reaches or exceeds desiredTotal, current player wins.
    • Otherwise, recursively check if the opponent loses in the next state.
  • If any pick leads to a win, return true; else, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
   bool canIWin(int n, int total) {
      if ((n + 1) * n / 2 < total) return false;
      if (total == 0) return true;
      std::unordered_map<int, bool> memo;
      std::function<bool(int, int)> dfs = [&](int mask, int rem) {
        if (memo.count(mask)) return memo[mask];
        for (int i = 0; i < n; ++i) {
           if (!(mask & (1 << i))) {
              if (i + 1 >= rem || !dfs(mask | (1 << i), rem - (i + 1)))
                return memo[mask] = true;
           }
        }
        return memo[mask] = false;
      };
      return dfs(0, total);
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func canIWin(n int, total int) bool {
   if (n+1)*n/2 < total {
      return false
   }
   if total == 0 {
      return true
   }
   memo := map[int]bool{}
   var dfs func(mask, rem int) bool
   dfs = func(mask, rem int) bool {
      if v, ok := memo[mask]; ok {
        return v
      }
      for i := 0; i < n; i++ {
        if mask&(1<<i) == 0 {
           if i+1 >= rem || !dfs(mask|(1<<i), rem-(i+1)) {
              memo[mask] = true
              return true
           }
        }
      }
      memo[mask] = false
      return false
   }
   return dfs(0, total)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
   public boolean canIWin(int n, int total) {
      if ((n + 1) * n / 2 < total) return false;
      if (total == 0) return true;
      Map<Integer, Boolean> memo = new HashMap<>();
      return dfs(0, total, n, memo);
   }
   private boolean dfs(int mask, int rem, int n, Map<Integer, Boolean> memo) {
      if (memo.containsKey(mask)) return memo.get(mask);
      for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) {
           if (i + 1 >= rem || !dfs(mask | (1 << i), rem - (i + 1), n, memo)) {
              memo.put(mask, true);
              return true;
           }
        }
      }
      memo.put(mask, false);
      return false;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
   fun canIWin(n: Int, total: Int): Boolean {
      if ((n + 1) * n / 2 < total) return false
      if (total == 0) return true
      val memo = mutableMapOf<Int, Boolean>()
      fun dfs(mask: Int, rem: Int): Boolean {
        memo[mask]?.let { return it }
        for (i in 0 until n) {
           if (mask and (1 shl i) == 0) {
              if (i + 1 >= rem || !dfs(mask or (1 shl i), rem - (i + 1))) {
                memo[mask] = true
                return true
              }
           }
        }
        memo[mask] = false
        return false
      }
      return dfs(0, total)
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
   def canIWin(self, n: int, total: int) -> bool:
      if (n + 1) * n // 2 < total:
        return False
      if total == 0:
        return True
      memo: dict[int, bool] = {}
      def dfs(mask: int, rem: int) -> bool:
        if mask in memo:
           return memo[mask]
        for i in range(n):
           if not (mask & (1 << i)):
              if i + 1 >= rem or not dfs(mask | (1 << i), rem - (i + 1)):
                memo[mask] = True
                return True
        memo[mask] = False
        return False
      return dfs(0, total)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
   pub fn can_i_win(n: i32, total: i32) -> bool {
      if (n + 1) * n / 2 < total {
        return false;
      }
      if total == 0 {
        return true;
      }
      use std::collections::HashMap;
      fn dfs(mask: i32, rem: i32, n: i32, memo: &mut HashMap<i32, bool>) -> bool {
        if let Some(&ans) = memo.get(&mask) {
           return ans;
        }
        for i in 0..n {
           if mask & (1 << i) == 0 {
              if i + 1 >= rem || !dfs(mask | (1 << i), rem - (i + 1), n, memo) {
                memo.insert(mask, true);
                return true;
              }
           }
        }
        memo.insert(mask, false);
        false
      }
      let mut memo = HashMap::new();
      dfs(0, total, n, &mut memo)
   }
}

Complexity

  • ⏰ Time complexity: O(2^n * n) (since there are 2^n states and for each state up to n choices)
  • 🧺 Space complexity: O(2^n) (for memoization)