# 464. Can I Win

## Description

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.

Example 1:

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:

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


Example 3:

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


Constraints:

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

## Solutions

• class Solution {
private Map<Integer, Boolean> memo = new HashMap<>();

public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
if (s < desiredTotal) {
return false;
}
return dfs(0, 0, maxChoosableInteger, desiredTotal);
}

private boolean dfs(int state, int t, int maxChoosableInteger, int desiredTotal) {
if (memo.containsKey(state)) {
return memo.get(state);
}
boolean res = false;
for (int i = 1; i <= maxChoosableInteger; ++i) {
if (((state >> i) & 1) == 0) {
if (t + i >= desiredTotal
|| !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal)) {
res = true;
break;
}
}
}
memo.put(state, res);
return res;
}
}

• class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
if (s < desiredTotal) return false;
unordered_map<int, bool> memo;
return dfs(0, 0, maxChoosableInteger, desiredTotal, memo);
}

bool dfs(int state, int t, int maxChoosableInteger, int desiredTotal, unordered_map<int, bool>& memo) {
if (memo.count(state)) return memo[state];
bool res = false;
for (int i = 1; i <= maxChoosableInteger; ++i) {
if ((state >> i) & 1) continue;
if (t + i >= desiredTotal || !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal, memo)) {
res = true;
break;
}
}
memo[state] = res;
return res;
}
};

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

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


• func canIWin(maxChoosableInteger int, desiredTotal int) bool {
s := (1 + maxChoosableInteger) * maxChoosableInteger / 2
if s < desiredTotal {
return false
}
memo := map[int]bool{}
var dfs func(int, int) bool
dfs = func(state, t int) bool {
if v, ok := memo[state]; ok {
return v
}
res := false
for i := 1; i <= maxChoosableInteger; i++ {
if (state>>i)&1 == 1 {
continue
}
if t+i >= desiredTotal || !dfs(state|1<<i, t+i) {
res = true
break
}
}
memo[state] = res
return res
}
return dfs(0, 0)
}

• function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
if (((1 + maxChoosableInteger) * maxChoosableInteger) / 2 < desiredTotal) {
return false;
}
const f: Record<string, boolean> = {};
const dfs = (mask: number, s: number): boolean => {
}
for (let i = 1; i <= maxChoosableInteger; ++i) {
if (((mask >> i) & 1) ^ 1) {
if (s + i >= desiredTotal || !dfs(mask ^ (1 << i), s + i)) {