## Algorithm

Problem Name: 464. Can I Win

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int canWin(int *dp, int v, int m, int total) {
int i, hewins;

if (dp[v] != -1) return dp[v];      // already resolved

for (i = m; i >= 1; i --) {
if (v & (1 << (i - 1))) continue;
v |= (1 << (i - 1));
if (i >= total) {
dp[v] = 1;          // resolve to win
return 1;
}
hewins = canWin(dp, v, m, total - i);
if (!hewins) return 1;
v &= ~(1 << (i - 1));   // not able to resolve, try with different number
}
dp[v] = 0;      // resolve to loose
return 0;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
int w, dp[1 << 20];

// none can win
if (maxChoosableInteger * (maxChoosableInteger + 1) / 2  <  desiredTotal) return false;

//dp = calloc((1 << (maxChoosableInteger)), sizeof(int));
//assert(dp);
memset(dp, -1, (1 << (maxChoosableInteger)) * sizeof(int));

w = canWin(dp, 0, maxChoosableInteger, desiredTotal);

//free(dp);

return w;
}
``````
Copy The Code &

Input

cmd
maxChoosableInteger = 10, desiredTotal = 11

Output

cmd
false

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const canIWin = function(maxChoosableInteger, desiredTotal) {
if (desiredTotal <= 0) return true
if ((maxChoosableInteger * (1 + maxChoosableInteger)) / 2 < desiredTotal)
return false
const dp = new Array(1 << maxChoosableInteger).fill(0)
return dfs(dp, 0, maxChoosableInteger, desiredTotal)

function dfs(dp, chs, max, target) {
if (target  < = 0) return false
if (dp[chs] != 0) return dp[chs] === 1
let win = false
for (let i = 0; i < max; i++) {
if ((chs & (1 << i)) === 0) {
//not used
win = win || !dfs(dp, chs ^ (1 << i), max, target - i - 1)
}
}
dp[chs] = win ? 1 : -1
return win
}
}
``````
Copy The Code &

Input

cmd
maxChoosableInteger = 10, desiredTotal = 11

Output

cmd
false

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def canIWin(self, maxChoosableInteger, desiredTotal):
memo = {}
def dfs(arr, total):
s = str(arr)
if s in memo:
return memo[s]
elif arr[-1] >= total:
return True
for i in range(len(arr)):
if not dfs(arr[:i] + arr[i + 1:], total - arr[i]):
memo[s] = True
return True
memo[s] = False
return False
if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
return dfs(list(range(1, maxChoosableInteger + 1)), desiredTotal)
``````
Copy The Code &

Input

cmd
maxChoosableInteger = 10, desiredTotal = 0

Output

cmd
true