<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>

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # if desiredTotal>(maxChoosableInteger)*(maxChoosableInteger+1)/2: return False
        # @cache
        # def foo(choices,remaining):
        #     if choices[-1]>=remaining: return True
        #     for i in range(len(choices)):
        #         if not foo(choices[:i]+choices[i+1:],remaining-choices[i]): return True
        #     return False
        # return foo(tuple([i for i in range(1,maxChoosableInteger+1)]),desiredTotal)

        # if maxChoosableInteger >= desiredTotal or desiredTotal <= 0:
        #     return True
        if desiredTotal>(maxChoosableInteger)*(maxChoosableInteger+1)/2: 
            return False
        elif desiredTotal == (maxChoosableInteger)*(maxChoosableInteger+1)/2:
            return maxChoosableInteger % 2 == 1
        if maxChoosableInteger >= desiredTotal:
            return True
        @lru_cache(None)
        def dfs(bitmask,total):
            for i in range(1,maxChoosableInteger+1):
                if (bitmask&(1<<i)) == 0:
                    if total + i >= desiredTotal or not dfs(bitmask|(1<<i),total+i):
                        return True 

            return False  

        return ((1+maxChoosableInteger)*maxChoosableInteger)//2 >= desiredTotal and dfs(0,0)

        memo = {}
        def canWin(choices, remaining):
            if choices[-1] >= remaining:
                return True
            if choices in memo:
                return memo[choices]
            for i in range(len(choices)):
                if not canWin(choices[:i]+choices[i+1:], remaining - choices[i]):
                    memo[choices] = True
                    return True
            memo[choices] = False
            return False
        choices = tuple([i for i in range(1, maxChoosableInteger+1)])
        return canWin(choices, desiredTotal)
189743