# Can I Win
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/can-i-win)
Canonical: https://scaleengineer.com/dsa/problems/can-i-win
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## 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**.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

# Approaches
## Brute-Force Recursion
This approach models the game by exploring every possible sequence of moves using a recursive function. It directly translates the game's rules into a recursive structure without any optimization for repeated computations. It represents the game tree and explores every path to determine if a winning strategy exists for the first player.
**Time:** O(N!), where N is `maxChoosableInteger`. The function explores all permutations of numbers, leading to a factorial number of paths in the game tree. · **Space:** O(N), where N is `maxChoosableInteger`. This space is used for the recursion stack depth and to store the set of used numbers.
**Pros:** Simple to understand and implement as it directly models the game logic.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; The time complexity is factorial, making it infeasible for the given constraints.; Will result in a 'Time Limit Exceeded' error on most coding platforms.
### Explanation
This approach models the game by exploring every possible sequence of moves using a recursive function. It directly translates the game's rules into a recursive structure without any optimization for repeated computations.

- We define a recursive function, say `canWinRecursive(usedNumbers, currentTotal)`, which returns `true` if the current player can force a win given the set of `usedNumbers` and the `currentTotal`.
- In each call, the function iterates through all numbers from 1 to `maxChoosableInteger`.
- For each available number, it simulates picking that number.
- If picking a number `i` makes the `currentTotal + i` reach or exceed `desiredTotal`, the current player wins.
- Otherwise, it makes a recursive call for the opponent's turn with the updated set of used numbers and the new total. The current player wins if the opponent *loses* in the subsequent state (i.e., the recursive call returns `false`).
- If after trying all available numbers, no winning move is found, the current player loses.
- This method explores the entire game tree, which includes many redundant calculations for the same game states reached through different sequences of moves.

```java
// Conceptual code for brute-force recursion
private boolean canWinRecursive(java.util.Set<Integer> used, int currentTotal, int maxChoosableInteger, int desiredTotal) {
    // Iterate through all possible numbers
    for (int i = 1; i <= maxChoosableInteger; i++) {
        // If the number is not used yet
        if (!used.contains(i)) {
            // Check if this move wins
            if (currentTotal + i >= desiredTotal) {
                return true;
            }
            
            // Make the move and recurse for the other player
            used.add(i);
            // If the other player CANNOT win, then this is a winning move for us
            if (!canWinRecursive(used, currentTotal + i, maxChoosableInteger, desiredTotal)) {
                used.remove(i); // Backtrack
                return true;
            }
            used.remove(i); // Backtrack
        }
    }
    // If no winning move is found
    return false;
}
```
### Algorithm
- Create a recursive function `canWin(usedNumbers, currentTotal)`.
- Loop from `i = 1` to `maxChoosableInteger`.
- If `i` is not in `usedNumbers`:
    - If `currentTotal + i >= desiredTotal`, return `true` as this is a winning move.
    - Recursively call `canWin` for the opponent: `opponentLoses = !canWin(usedNumbers + {i}, currentTotal + i)`.
    - If `opponentLoses` is `true`, it means we found a move that guarantees a win. Return `true`.
- If the loop finishes without finding a winning move, it means all moves lead to the opponent winning. Return `false`.

## Top-Down Dynamic Programming with Memoization
This approach optimizes the recursive solution by using memoization to store and reuse the results of subproblems. A subproblem is uniquely defined by the set of numbers that have already been used. This avoids re-computing the outcome for the same game state multiple times, drastically improving efficiency.
**Time:** O(N * 2^N), where N is `maxChoosableInteger`. Each of the `2^N` states is computed once. Inside each computation, we loop up to `N` times to find an available number. · **Space:** O(2^N), where N is `maxChoosableInteger`. This space is dominated by the memoization table. The recursion depth adds O(N), which is negligible.
**Pros:** Efficient enough to pass within the given constraints by avoiding redundant computations.; Correctly solves the problem by applying the minimax principle with memoization.; The use of a bitmask for state representation is highly efficient in both time and space for small N.
**Cons:** The space complexity is exponential, `O(2^N)`, which might be a concern for larger values of `maxChoosableInteger` (though it's fine for N <= 20).
### Explanation
The key observation is that the outcome of the game from any point depends only on the set of available numbers, not the order in which previous numbers were picked. This allows us to memoize results for game states.

- **State Representation**: We can represent the set of used numbers efficiently using a bitmask. A bitmask is an integer where the `i-1`-th bit is set to 1 if the number `i` has been used, and 0 otherwise. Since `maxChoosableInteger` is at most 20, a single 32-bit integer is sufficient to represent any state.
- **Memoization**: We use a memoization table, `Boolean[] memo`, of size `2^maxChoosableInteger`. `memo[mask]` will store `true` if the current player can win from the state represented by `mask`, and `false` otherwise.
- **Recursive Helper**: A recursive function, `canWinHelper(mask, remainingTotal)`, is defined. `mask` represents the used numbers, and `remainingTotal` is the target sum to reach.
- The function first checks the memoization table. If the result for the current `mask` is already computed, it returns the stored value.
- It then iterates from 1 to `maxChoosableInteger`. For each available number `i`, it simulates picking it.
- The current player wins if they can find a move `i` such that the opponent cannot win from the resulting state. This is checked by a recursive call: `!canWinHelper(newMask, remainingTotal - i)`.
- If a winning move is found, the result (`true`) is stored in the memoization table for the current `mask`, and `true` is returned.
- If all possible moves are explored and none lead to a win, the result (`false`) is stored, and `false` is returned.
- Initial edge cases are handled first: if the total sum of all numbers is less than `desiredTotal`, it's impossible to win.

```java
class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) {
            return true;
        }
        if ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2 < desiredTotal) {
            return false;
        }
        
        Boolean[] memo = new Boolean[1 << maxChoosableInteger];
        return canWinHelper(0, desiredTotal, maxChoosableInteger, memo);
    }

    private boolean canWinHelper(int mask, int remainingTotal, int maxChoosableInteger, Boolean[] memo) {
        if (remainingTotal <= 0) {
            return false; // Previous player won
        }
        if (memo[mask] != null) {
            return memo[mask];
        }

        for (int i = 1; i <= maxChoosableInteger; i++) {
            // Check if the bit for number `i` is not set in the mask.
            // The bit for number `i` is at position `i-1`.
            if ((mask & (1 << (i - 1))) == 0) {
                // If the opponent cannot win from the next state, then we win.
                if (!canWinHelper(mask | (1 << (i - 1)), remainingTotal - i, maxChoosableInteger, memo)) {
                    memo[mask] = true;
                    return true;
                }
            }
        }

        memo[mask] = false;
        return false;
    }
}
```
### Algorithm
- Handle edge cases: if `desiredTotal <= 0`, return `true`. If the sum of all choosable numbers is less than `desiredTotal`, return `false`.
- Create a memoization array `memo` of size `2^maxChoosableInteger` to store results of subproblems.
- Define a recursive helper function `canWinHelper(mask, remainingTotal)`.
- Inside the helper function:
    - If `remainingTotal <= 0`, it means the previous player won, so the current player loses. Return `false`.
    - If `memo[mask]` is already computed, return the stored value.
    - Loop `i` from 1 to `maxChoosableInteger`.
    - If number `i` has not been used (check the `mask`):
        - Make a recursive call for the opponent: `canWinHelper(newMask, remainingTotal - i)`.
        - If the opponent loses (the call returns `false`), it means the current move is a winning one. Set `memo[mask] = true` and return `true`.
- If the loop completes without finding a winning move, the current player cannot force a win from this state. Set `memo[mask] = false` and return `false`.
- Start the process by calling `canWinHelper(0, desiredTotal)`.

# Solutions
### Java

```java
class Solution {
private
  Map<Integer, Boolean> memo = new HashMap<>();
public
  boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
    if (s < desiredTotal) {
      return false;
    }
    return dfs(0, 0, maxChoosableInteger, desiredTotal);
  }
private
  boolean dfs(int state, int t, int maxChoosableInteger, int desiredTotal) {
    if (memo.containsKey(state)) {
      return memo.get(state);
    }
    boolean res = false;
    for (int i = 1; i <= maxChoosableInteger; ++i) {
      if (((state >> i) & 1) == 0) {
        if (t + i >= desiredTotal ||
            !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal)) {
          res = true;
          break;
        }
      }
    }
    memo.put(state, res);
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canIWin(int maxChoosableInteger, int desiredTotal) {
    int s = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
    if (s < desiredTotal)
      return false;
    unordered_map<int, bool> memo;
    return dfs(0, 0, maxChoosableInteger, desiredTotal, memo);
  }
  bool dfs(int state, int t, int maxChoosableInteger, int desiredTotal,
           unordered_map<int, bool> &memo) {
    if (memo.count(state))
      return memo[state];
    bool res = false;
    for (int i = 1; i <= maxChoosableInteger; ++i) {
      if ((state >> i) & 1)
        continue;
      if (t + i >= desiredTotal ||
          !dfs(state | 1 << i, t + i, maxChoosableInteger, desiredTotal,
               memo)) {
        res = true;
        break;
      }
    }
    memo[state] = res;
    return res;
  }
};

```

### Python

```python
class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: @ cache def dfs(state, t): for i in range(1, maxChoosableInteger + 1): if (state >> i) & 1: continue if t + i >= desiredTotal or not dfs(state | 1 << i, t + i): return True return False s = (1 + maxChoosableInteger) * maxChoosableInteger // 2 if s < desiredTotal: return False return dfs(0, 0)

```