# Python solution, easy to understand

• Easy to understand baseline solution (not fast though), memorization is used to prune the search space.

``````    def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
self.memo = {}
return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)

def helper(self, nums, desiredTotal):

hash = str(nums)
if hash in self.memo:
return self.memo[hash]

if nums[-1] >= desiredTotal:
return True

for i in range(len(nums)):
if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
self.memo[hash]= True
return True
self.memo[hash] = False
return False``````

• @bugdx Thanks for the idea. easy to understand for beginners like me.

• This post is deleted!

• Nice. The second player's state is described by

``````if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
``````

and the conclusion of which is used to determine the state of the first player, a smart solution.

• I don't understand the logic below. Does it imply that a player could no number in a round?

``````        if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
``````

• @jedihy That means even the sum of all available numbers is still smaller than the target, so it is impossible to win.

• @SNSN2033 but in such a situation, the second player cannot win as well?

• This is my code. I did not have the extra condition before and it cannot pass for test case like 5, 50.

``````class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
def helper(pool, target, visited):
if pool in visited:
return visited[pool]
if target <= 0:
return False

for i in xrange(0, maxChoosableInteger):
if pool & mask == 0:
if helper(newPool, target - (i + 1), visited) == False:
visited[pool] = True
return True
visited[pool] = False
return False

# extra condition
if (1 + maxChoosableInteger) * (maxChoosableInteger / 2) < desiredTotal:
return False
# extra condition

if desiredTotal == 0:
return True
pool = 0
visited = {}
return helper(pool, desiredTotal, visited)
``````

• @jedihy No he can't. But this problem only asks us "whether we can make player 1 win".

• @SNSN2033 I expected that the DFS procedure can automatically count this situation. But it seems that I am wrong. Every posted solution check this condition at the beginning.

• Hi @bugdx ,
The cache does not include the desiredTotal, do we need more test case or there is a reason that your solution works?
For example, say (maxChoosableInteger is 5 and desiredTotal is 10) these two cached values would have the same result even though they are different:

1. cache['1,3,5'], desiredTotal 4 (2, 4 used)
2. cache['2,3,4'], desiredTotal 4 (1, 5 used)

• Thanks. I didn't understand the other's solutions. But I understand yours.

• Hi, @yang2007chun .
The memory is used to store the visited <State, Result> pairs, where the State is just the encoding of the current state and the Result is win or loss for current player to move. It's useful because if we meet a state again we don't need to search for the result of the state. For your question, there will be many caches have the same result because there are just 2 results (w or l) but there are many more possible states.

Also, I just used remaining numbers to encode the state for two reasons:

1. we do not need to encode the information of which player to move because for given set of numbers, if the parity of current state is the same as initial state, it's first player's turn. Otherwise it's the second player's turn.
2. we do not need to encode the desiredTotal because it's the same for all states. It's like if we need to encode a Chess board we just need a list of remaining pieces and their positions and we don't need the board size since it's always 8 x 8 for all states.

Hope this post will be helpful.

• How do we prove this algorithm has time complexity O(2^N)?

• How do we prove this algorithm has time complexity O(2^N)?

The value `2^N` comes from the number of states in this game. Note that a state of the game is completely determined by the still available numbers in the pool, which is a subset of the initial pool `[1, N]`, where `N = maxChoosableInteger`, and the number of subsets is exactly `2^N`.

With memorization during DFS, it guarantees that we solve each state (i.e., sub-problem) of the game at most once (note that we could early return from DFS if e.g., `desiredTotal` is significantly small compared to sum of `[1, N]`). You can image each state is a node if a binary tree, root is the initial state and leaf is the base case for DFS to return. For base case, we solve it in `O(1)` time, obviously. And the DFS just passed lower level results back to upper level until back to the root. So the total time is the total number of nodes in a binary tree with maximum depth `N`, i.e., `O(2^N)`.

I have a post below to further explain the definition of a game state if you are interested:
10-liner concise C++ beat 98.4% recursive solution with early termination check, no helpers (detailed explanation)

• There should be another case for early termination which should be checked:

• if the sum of total from initial pool [1, max] is equal to the desired total, then return max%2 directly.

In this case, the order to pick number is totally irrelevant. Whoever picks the last number from pool wins, so first player wins iff there are odd count of integers in the pool initially.

• 20
210

index out of range for the above test case

• @bugdx can you please explain a logic a little bit?

What does self.memo[hash] contain? Why is it set to True in this loop

``````            if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
self.memo[hash]= True
return True
``````

Also, when we reach this condition - what does it mean?

``````        if nums[-1] >= desiredTotal:
return True
``````

Here is my stab at understanding this solution -

``````    def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""

# if 1+2+3+....+maxChoosableInteger < desiredTotal, then no player can ever acquire desiredTotal, returning False
if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
return False
self.memo = {}
return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)

def helper(self, nums, desiredTotal):
"""
:param num:              available number pool
:param desiredTotal:  desired total for victory
"""
hash = str(nums)
if hash in self.memo:
return self.memo[hash] # if number pool is already evaluated, return memoized answer

if nums[-1] >= desiredTotal:   # if available number pool has desiredTotal (at the end? why?), then we're winning (what about self.memo? why not setting True here?)
return True

for i in range(len(nums)):
# pick each number in the number pool, and see using that if we attain desired Total
if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]): # whats the meaning of this condition?? why is this  ( "not" self.helper())?
self.memo[hash]= True
return True
self.memo[hash] = False
return False
``````

• This post is deleted!

• @parvez.h.shaikh I try to go through the detail and now I think i kind of get it.

``````            if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
self.memo[hash]= True
return True
``````

the dict memo contain the available number we can choose and the target number we want to get.

``````     self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i])
``````

represent the state of the second player and if there exist one state that he is guarantees to loose, the first player can force a win assuming both players play optimally.

``````     self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i])
``````

here I think it means at some condition both player can't win.
like [4,5,6,7] target = 9: if the first player choose 6 or 7, both player can't win, however, here we use the second player's state to determine the first player's result, if we set state as false, as I explain above, the first player will think he can win definitely. So we set this state as True.
I am not sure if I am correct and I am new to python.
Please correct me if i am wrong.

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