> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Can I Win Python Solution with Tests

> Tested Python solution for LeetCode 464 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 464, [Medium](/catalog/medium). Topics: [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), [Bit Manipulation](/catalog/topics/bit-manipulation), [Memoization](/catalog/topics/memoization), [Game Theory](/catalog/topics/game-theory), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/can-i-win/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 464   # by problem number
lcpy gen -s can_i_win   # by problem name
```

## Problem

In the "100 game" two players take turns adding, to a running total, any integer from `1` to `10`. The player who first causes the running total to **reach or exceed** 100 wins.

What if we change the game so that players **cannot** re-use integers?

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 >= 100.

Given two integers `maxChoosableInteger` and `desiredTotal`, return `true` if the first player to move can force a win, otherwise, return `false`. Assume both players play optimally.

### Examples

```
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
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 >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
```

```
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
```

```
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
```

### Constraints

* 1 \<= maxChoosableInteger \<= 20
* 0 \<= desiredTotal \<= 300

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/can_i_win/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/can_i_win/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(2^m * m) where m = max_choosable_integer
    # Space: O(2^m)
    def can_i_win(self, max_choosable_integer: int, desired_total: int) -> bool:
        if desired_total <= 0:
            return True
        pool = max_choosable_integer * (max_choosable_integer + 1) // 2
        if pool < desired_total:
            return False

        memo: dict[int, bool] = {}

        def dfs(used: int, remaining: int) -> bool:
            if used in memo:
                return memo[used]
            for choice in range(max_choosable_integer):
                bit = 1 << choice
                if used & bit:
                    continue
                if choice + 1 >= remaining or not dfs(used | bit, remaining - choice - 1):
                    memo[used] = True
                    return True
            memo[used] = False
            return False

        return dfs(0, desired_total)
```

## Complexity

| Time | Space |
| - | - |
| O(2^m \* m) where m = max\_choosable\_integer | O(2^m) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.