package _464;

class Solution {
    // maxChoosableInteger will not be larger than 20,
    // and desiredTotal will not be larger than 300
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        return canIWinIter(maxChoosableInteger, desiredTotal, 0, 0, true);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canIWin(10, 11));
        System.out.println(s.canIWin(10, 0));
    }

    private boolean canIWinIter(int maxChoosableInteger, int desiredTotal, int intChoosen, int total,
            boolean isMyTurn) {
        if (total >= desiredTotal) {
            System.out.println(total);
            if (isMyTurn) {
                return true;
            }
            return false;
        }
        for (int i = 0; i < maxChoosableInteger; i++) {
            boolean isChoosen = (intChoosen & (1 << i)) != 0;
            if (isChoosen) {
                continue;
            }
            boolean iCanWin = canIWinIter(maxChoosableInteger, desiredTotal, intChoosen | (1 << i), total + i + 1,
                    !isMyTurn);
            if (iCanWin) {
                return true;
            }
        }
        return false;
    }
}