# 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.
• 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:

Code: