Python DFS, very easy to understand.

  • 0
    class Solution(object):
        def canIWin(self, maxChoosableInteger, desiredTotal):
            choosable = tuple(range(1, maxChoosableInteger + 1))
            if sum(choosable) < desiredTotal: return False
            self.cache = {}
            return self.dfs(choosable, desiredTotal)
        def dfs(self, choosable, total):
            if choosable[-1] >= total: return True
            key = choosable
            if key in self.cache: return self.cache[key]
            for i in range(len(choosable)):
                if not self.dfs(choosable[:i] + choosable[i + 1:], total - choosable[i]):
                    self.cache[key] = True
                    return True
            self.cache[key] = False
            return False

  • 0

    @zhongyuan9817 : Could you please explain your solution?

Log in to reply

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