**Solution**

**Can I Win** https://leetcode.com/problems/can-i-win/

**Top Down DFS with Memoization: Time: O(N * 2^N). Space: O(2^N)**

- We create an array allowed which has all the integers from 1 to maxChoosableInteger.
- We test if the input is valid or not i.e. sum(allowed) >= desiredTotal.
- How do we define the state of the game? This answer determines how we will do memoization as well. Clearly list of current allowed numbers are needed to define the state. It might also look that so_far is also required to define the state. However, given all allowed values and the current set of allowed values, so_far is really the difference of the sum of the two. Therefore only allowed values uniquely determine the state.
- How many allowed values sets are possible? The length of the allowed value set can range 1 to maxChoosableInteger(N). So the answer is (N,1) + (N,2) + ..(N,N) where (N,K) means choose K from N. This is equal to 2^N.
- Now at my turn, if the max(allowed) + so_far >= target, then I will win. Otherwise, I choose from the allowed values one by one and recursively call for the other player. If with any choice the opponent fails for sure, then also I can win for sure from this state.
- What is the time complexity? For a brute force solution, the game tree has 10 choices at first level, each of these choices has 9 choices at second level, and so on. So the complexity is N!. But with memoization, we only compute 2^N sub-problems, and in each problem we do O(N) work. So total time complexity is O(N2^N).

```
class Solution(object):
def helper(self, allowed, target, so_far, cache):
if len(allowed) == 0:
return False
state = tuple(allowed)
if state in cache:
return cache[state]
else:
cache[state] = False
if max(allowed) + so_far >= target:
cache[state] = True
else:
for x in allowed:
new_allowed = [y for y in allowed if x!=y]
if self.helper(new_allowed, target, so_far+x, cache) == False:
cache[state] = True
break
return cache[state]
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
allowed = [x for x in range(1, maxChoosableInteger+1)]
if sum(allowed) < desiredTotal:
return False
return self.helper(allowed, desiredTotal, 0, {})
```