My solution using List of HashMaps


  • 0
    J
    class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if(maxChoosableInteger >= desiredTotal) return true;
            if (maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return false;
            List<HashMap<Integer, Boolean>> memo = new ArrayList<>();
            for(int i = 0; i <= desiredTotal; i++){
                HashMap<Integer, Boolean> map = new HashMap<>();
                memo.add(map);
            }
            // the first integer represents current goal, and hashmap's integer represents boolean array used 
            boolean[] used = new boolean[maxChoosableInteger+ 1];
            return helper(maxChoosableInteger, desiredTotal, memo, used); 
        }
        
        private boolean helper(int choose, int goal, List<HashMap<Integer, Boolean>> memo, boolean[] used){
            int usedint = format(used);
            if(memo.get(goal).containsKey(usedint)) return memo.get(goal).get(usedint);
            
            for(int i = 1; i <= choose; i++){
                if(used[i]) continue;
                used[i] = true;
                if(goal - i <= 0 || !helper(choose, goal - i, memo, used)){
                    memo.get(goal).put(usedint, true);
                    used[i] = false;
                    return true;
                }
                used[i] = false; 
            }
            memo.get(goal).put(usedint, false);
            return false;
        } 
        
        private int format(boolean[] used){
            int number = 0;
            for(boolean u : used){
                number <<= 1;
                if(u) number |= 1;
            }
            
            return number;
        }
    }
    

Log in to reply
 

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