Clear Java Recursive Solution Using HashMap and BitMask


  • 0

    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);
        }
    }

Log in to reply
 

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