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

    private static void testCanIWin(int maxChoosableInteger, int desiredTotal) {
        Solution solution = new Solution();
        System.out.println(solution.canIWin(maxChoosableInteger, desiredTotal));
    }

    public static void main(String[] args) {
        testCanIWin(10, 11);
        testCanIWin(2, 3);
    }

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