# Clear Java Recursive Solution Using HashMap and BitMask

• The idea is straight-forward, just simulate every possible outcome, for each player's turn, evaluate if the opponent will win with the left numbers. However, there are many common sub-problems (same set of left numbers with same total), use HashMap to keep them and re-use. This is dynamic programming. And to encode it well, I used an Integer bitmap to represent the usage of numbers.

``````public class Solution {

Map<Integer,Boolean> mem = new HashMap<>();

private boolean helper(int[] choices, int bitMap, int total) {
for(int i=choices.length-1; i>=0; i--)
if((bitMap>>>(32-i-1))%2==0 && choices[i]>=total)
return true;
if(mem.containsKey(bitMap))
return mem.get(bitMap);
for(int i=choices.length-1; i>=0; i--) {
if((bitMap>>>(32-i-1))%2==0) {
if(!helper(choices, bitMap | (1<<(32-i-1)), total-choices[i])) {
mem.put(bitMap,true);
return true;
}
}
}
mem.put(bitMap,false);
return false;
}

public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if(desiredTotal <= maxChoosableInteger)
return true;
else if(desiredTotal > maxChoosableInteger*(maxChoosableInteger+1)/2)
return false;
int[] choices = new int[maxChoosableInteger];
for(int i=0; i<choices.length; i++)
choices[i] = i+1;
return helper(choices, 0, desiredTotal);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.