class Solution {
    private int NUM_OF_MOVES = 0;
    //private Map<int[], int> cache = new HashMap<int[], int>();
    private int runningSum = 0;

    public boolean helper(int maxChoosableInteger, int desiredTotal, int[] takens) {
        boolean resPlayer1 = false;

        for(int i = 0; i < maxChoosableInteger-1; i++) {
            if (takens[i] == 1) continue;
            int chosenVal = i+1;
            takens[i] = 1;
            runningSum += chosenVal;
            if (runningSum >= desiredTotal && NUM_OF_MOVES % 2 == 0) return true;
            //cache.add(takens, runningSum);
            NUM_OF_MOVES += 1;
            if (NUM_OF_MOVES %2 == 0) resPlayer1 = helper(maxChoosableInteger, desiredTotal, takens);
            NUM_OF_MOVES -=1;
            takens[i] = 0;
            runningSum -= chosenVal;
            if (resPlayer1 == true) return true;
        }
        return resPlayer1;
    }

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int[] takens = new int[maxChoosableInteger];
        Arrays.fill(takens, 0);
        return helper(maxChoosableInteger, desiredTotal, takens);

    }
}