464. Can I Win

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if sum(range(1,maxChoosableInteger+1))<desiredTotal:
            return False 
        self.memo=dict()
        return self.helper(range(1,maxChoosableInteger+1),desiredTotal)
    def helper(self,array,desiredTotal):
        array_hash=str(array)
        #this is memoization, if this subproblem has already been calculated then return directly
        if array_hash in self.memo:
            return self.memo[array_hash]
        #this is the base case of the problem. if it is my turn and the max number in the array is enough to reach the desiredTotal , then i can force a win by simply picking this max number 
        if array[-1]>=desiredTotal:
            self.memo[array_hash]=True
            return True
            
        #pick a number, if the opponent can't force a win with the rest, that means i can force a win with picking this number 
        for i in xrange(len(array)):
            if not self.helper(array[:i]+array[i+1:],desiredTotal-array[i]):
                self.memo[array_hash]=True
                return True 
        #if there is no number that i can pick to force a win, then this array, total combination is false. 
        self.memo[array_hash]=False
        return False