LeetCode [464] Can I Win

 464. Can I Win

Medium

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

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

class Solution { Map<Integer, Boolean> map = new HashMap<>(); int n; public boolean canIWin(int maxChoosableInteger, int desiredTotal) { if(desiredTotal<=0) return true; this.n = maxChoosableInteger; int sum = (1+n)*n/2; if(sum<desiredTotal) return false; return helper(0, desiredTotal); } boolean helper(int state, int total){ if(map.containsKey(state)) return map.get(state); for(int i=0; i<n; ++i){ if((state & (1<<i)) > 0) continue; int nextNumber = i+1; //winning if //1. the chosen number is >= current total //2. the next player will lose if(nextNumber>=total || !helper(state|(1<<i), total-nextNumber)){ map.put(state, true); return true; } } map.put(state, false); return false; } }