Concise Memoization Java Solution


  • 0
    K
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal)
            return false;
        Set<Integer> cache = new HashSet<Integer>();
        return canWin(0, maxChoosableInteger, desiredTotal, cache);
    }
    
    private boolean canWin(int code, int max, int total, Set<Integer> cache) {
        if (cache.contains(code))
            return false;
        for (int i = 0; i < max; i++) {
            if ((code & (1<<i)) == 0) {
                code |= (1<<i);
                if (i+1 >= total || !canWin(code, max, total-i-1, cache))
                    return true;
                code &= ~(1<<i);
            }
        }
        cache.add(code);
        return false;
    }

Log in to reply
 

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