Java fast solution


  • 0
    M
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(desiredTotal == 0) return true;
        if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        
        int remaining = 1 << maxChoosableInteger;
        BitSet computed = new BitSet(remaining);
        BitSet canWin = new BitSet(remaining);
    
        return helper(computed, canWin, remaining - 1, desiredTotal, maxChoosableInteger);
    
    }
    
    private static boolean helper(BitSet computed, BitSet canWin, int remaining, int desiredTotal, int max) {
        if(desiredTotal <= 0)
            return false;
    
        if(computed.get(remaining))
            return canWin.get(remaining);
    
        boolean win = false;
        for(int i = 0; i < max; i++) {
            int bit = 1 << i;
            if((remaining & bit) == 0) continue;
            if(!helper(computed, canWin, remaining - bit, desiredTotal - i - 1, max)) {
                win = true;
                break;
            }
        }
        computed.set(remaining);
        canWin.set(remaining, win);
    
        return win;
    }

Log in to reply
 

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