<p>In the &quot;100 game&quot; two players take turns adding, to a running total, any integer from <code>1</code> to <code>10</code>. The player who first causes the running total to <strong>reach or exceed</strong> 100 wins.</p>

<p>What if we change the game so that players <strong>cannot</strong> re-use integers?</p>

<p>For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total &gt;= 100.</p>

<p>Given two integers <code>maxChoosableInteger</code> and <code>desiredTotal</code>, return <code>true</code> if the first player to move can force a win, otherwise, return <code>false</code>. Assume both players play <strong>optimally</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> maxChoosableInteger = 10, desiredTotal = 11
<strong>Output:</strong> false
<strong>Explanation:</strong>
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is &gt;= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> maxChoosableInteger = 10, desiredTotal = 0
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> maxChoosableInteger = 10, desiredTotal = 1
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= maxChoosableInteger &lt;= 20</code></li>
	<li><code>0 &lt;= desiredTotal &lt;= 300</code></li>
</ul>

from collections import defaultdict
class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:


        # # # a typical dp problem 
        # n = maxChoosableInteger
        # choices = [i+1 for i in range(n)]

        # if sum(choices) < desiredTotal: 
        #     return False 

        # can_use = [1] *  n
        # # print(choices, can_use)
        # memo = defaultdict()

        # def dp(can_use, target): 

        #     if sum(can_use) == 0: 
        #         return False 

        #     for i in range(n): 
        #         if can_use[i] and choices[i] >= target: 
        #             return True 

        #     if str(can_use) in defaultdict(): 
        #         return memo[str(can_use)]
            
        #     # temp = True 
        #     for i in range(n): 
        #         if can_use[i] == 0: 
        #             continue 
        #         can_use[i] = 0 
        #         temp = dp(can_use, target - choices[i])
        #         can_use[i] = 1 
        #         if temp == False: 
        #             memo[str(can_use)] = True 
        #             return True 
        #     memo[str(can_use)] = False 
        #     return False  


        #     # if temp == True: 
        #     #     memo[str(can_use)] = True 
        #     #     return False 
        #     # else: 
        #     #     memo[str(can_use)] = False
        #     #     return True 

        # # dp(can_use, desiredTotal)
        # # print(can_use)
        
        # return dp(can_use, desiredTotal)

            
            





        n = maxChoosableInteger
        choices = [i+1 for i in range(n)]
        used = [False] * n 
        memo = defaultdict()
        # first try if there is no memo one, check if things can work out 
        
        if sum(choices) < desiredTotal: 
            return False 

        def dp(choices, desiredTotal): 

            # base case
            if len(choices) ==0 : 
                return False 
    
            if max(choices) >= desiredTotal: 
                return True 
            
            string = ""
            for i in range(1, n+1): 
                if i in choices: 
                    string += "1"
                else: 
                    string += "0"
        
            if string in memo: 
                return memo[string]

            # temp = True 
            for choice in choices: 
                new_choices = choices.copy()
                new_choices.remove(choice)
                temp = dp(new_choices, desiredTotal- choice)

                if temp == False: 
                    memo[string] = True
                    return True 
                # print(dp(new_choices, desiredTotal- choice))
            # if temp == True: 
            #     memo[string] = False 
            #     return False
            # else: 
            memo[string] = False 
            return False 
        return dp(choices, desiredTotal)


        
143954