# Leetcode 464 - Can I Win

`Note:`

- When to return
`true`

?- After choosing my num from
`[1, max]`

that has not been used. No matter what num next person chooses, he cannot win.

- After choosing my num from
- Based on the constraints of this problem, it looks like solvable through
`dfs`

. - There will be repetitive calculations, so we need
`memo`

. - Use
`Number`

‘s bit to memo instead of`[]`

. Because all dfs will share a same`[]`

and we don’t want that. (Pass by reference). - For i from
`[1, max]`

, use`(1 << i) & used`

to check if number`x`

has been used. If that bit is`1`

, it’s been used. - Key part:
`total <= i || !dfs(used | curr, total - i)`

, it means either we`win now`

, or`next player will never win`

, then we can return`true`

.

`Question:`

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 |

`Code:`

1 | /** |