# LeetCode 464: Can I Win

## Problem Restatement

We are given two integers:

```python
maxChoosableInteger
desiredTotal
```

There are numbers from `1` to `maxChoosableInteger`.

Two players take turns choosing one unused number.

Each chosen number is added to a running total.

The player who makes the running total reach or exceed `desiredTotal` wins.

Both players play optimally.

We need to return whether the first player can force a win. The official problem asks whether the first player can force a win given `maxChoosableInteger` and `desiredTotal`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `maxChoosableInteger` |
| Input | `desiredTotal` |
| Output | `True` if the first player can force a win |
| Rule | Each number can be chosen at most once |
| Win condition | First player to make total at least `desiredTotal` wins |

Function shape:

```python
def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
    ...
```

## Examples

Example 1:

```python
maxChoosableInteger = 10
desiredTotal = 11
```

The first player cannot force a win.

If the first player chooses any number `x`, the second player can choose `11 - x` when it is available and reach `11`.

Answer:

```python
False
```

Example 2:

```python
maxChoosableInteger = 10
desiredTotal = 0
```

The target has already been reached before any move.

Answer:

```python
True
```

Example 3:

```python
maxChoosableInteger = 10
desiredTotal = 1
```

The first player chooses `1` immediately.

Answer:

```python
True
```

## First Thought: Try Every Game

A direct way is to simulate every possible game.

On the first move, the player can choose any number from `1` to `maxChoosableInteger`.

Then the second player can choose any remaining number.

Then the first player chooses again.

This forms a game tree.

At each state:

1. If some available number reaches the target, the current player wins.
2. Otherwise, the current player tries a move that makes the opponent lose.

This is the correct idea, but without memoization it repeats many states.

## Problem With Plain Recursion

The same remaining numbers can be reached in different orders.

For example, choosing:

```python
1 then 3
```

and choosing:

```python
3 then 1
```

lead to the same set of used numbers.

The future game only depends on which numbers are used, not the order used to reach that state.

Without memoization, the recursion recomputes the same states many times.

Since `maxChoosableInteger <= 20`, we can represent the used numbers with a bitmask. This gives at most:

```python
2^20
```

states.

## Key Insight

A game state can be represented by the set of used numbers.

Use a bitmask:

```python
mask
```

If bit `i` is `1`, then number `i` has already been chosen.

For example:

```python
mask = 0b1010
```

means numbers `1` and `3` are used if we map number `i` to bit `i`.

At each state, the recursive function returns:

```python
True
```

if the current player can force a win from that state.

A move is winning if:

1. The chosen number reaches the target immediately.
2. Or after choosing it, the opponent is in a losing state.

## Important Early Checks

First, if:

```python
desiredTotal <= 0
```

then the first player wins immediately.

Second, compute the sum of all choosable numbers:

```python
total = maxChoosableInteger * (maxChoosableInteger + 1) // 2
```

If:

```python
total < desiredTotal
```

then even choosing all numbers cannot reach the target.

So the first player cannot win.

## Algorithm

Define:

```python
dfs(mask, remaining)
```

where:

| Parameter | Meaning |
|---|---|
| `mask` | Which numbers are already used |
| `remaining` | How much total is still needed to win |

The function returns whether the current player can force a win.

For each number `x` from `1` to `maxChoosableInteger`:

1. If `x` is already used, skip it.
2. If `x >= remaining`, the current player wins immediately.
3. Otherwise, choose `x` and recursively check the opponent's state.
4. If the opponent cannot win, the current player can force a win.

If no move works, return `False`.

Memoize results by `mask`.

We can memoize only by `mask` because `remaining` is determined by the original `desiredTotal` minus the sum of numbers already used.

## Correctness

At any turn, the current player wins immediately if they can choose an unused number at least as large as `remaining`.

If no immediate winning move exists, the current player needs to choose a number that leaves the opponent in a losing state.

The recursive function checks every legal unused number. For each choice, it asks whether the opponent can win from the resulting state.

If at least one choice makes the opponent lose, then the current player can force a win by choosing that number.

If every legal choice lets the opponent win, then no strategy can force a win for the current player.

The memoization stores the result for each used-number set. Since the future options depend only on which numbers remain, reusing this result is valid.

Therefore, `dfs(0, desiredTotal)` correctly returns whether the first player can force a win.

## Complexity

Let:

```python
m = maxChoosableInteger
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * 2^m)` | There are at most `2^m` masks, and each state tries up to `m` moves |
| Space | `O(2^m)` | Memoization stores one result per mask |

Since `m <= 20`, this is feasible.

## Implementation

```python
from functools import cache

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= 0:
            return True

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

        @cache
        def dfs(mask: int, remaining: int) -> bool:
            for x in range(1, maxChoosableInteger + 1):
                bit = 1 << x

                if mask & bit:
                    continue

                if x >= remaining:
                    return True

                if not dfs(mask | bit, remaining - x):
                    return True

            return False

        return dfs(0, desiredTotal)
```

## Code Explanation

We first handle the immediate win case:

```python
if desiredTotal <= 0:
    return True
```

Then we check whether reaching the target is possible at all:

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

The recursive function:

```python
dfs(mask, remaining)
```

answers whether the current player can win from the current state.

For each possible number:

```python
for x in range(1, maxChoosableInteger + 1):
```

we compute its bit:

```python
bit = 1 << x
```

If that bit is already set, the number was used:

```python
if mask & bit:
    continue
```

If choosing `x` reaches the target, the current player wins:

```python
if x >= remaining:
    return True
```

Otherwise, we move to the opponent's state:

```python
dfs(mask | bit, remaining - x)
```

If the opponent cannot win from there, the current player wins:

```python
if not dfs(mask | bit, remaining - x):
    return True
```

If every choice fails:

```python
return False
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canIWin(10, 11) is False
    assert s.canIWin(10, 0) is True
    assert s.canIWin(10, 1) is True
    assert s.canIWin(10, 40) is False
    assert s.canIWin(5, 50) is False
    assert s.canIWin(5, 6) is False
    assert s.canIWin(5, 5) is True
    assert s.canIWin(20, 210) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(10, 11)` | Standard losing case |
| `(10, 0)` | Target already reached |
| `(10, 1)` | Immediate first-move win |
| `(10, 40)` | Reachable total but losing strategy |
| `(5, 50)` | Sum of all numbers is too small |
| `(5, 6)` | Small game where first player cannot force win |
| `(5, 5)` | Immediate win by choosing `5` |
| `(20, 210)` | All numbers sum exactly to target, second player gets last move |