Problem Description

The "Can I Win" problem is a two-player game where players take turns picking unique integers from 1 to maxChoosableInteger. Each number can only be chosen once. The chosen numbers are added together, and the goal is to be the first to reach or exceed a given desiredTotal. The function must determine if the first player can guarantee a win, assuming both players play optimally.

• Each turn, a player picks any unused number between 1 and maxChoosableInteger.
• The chosen numbers are summed up as the game progresses.
• The first player to make the total reach or exceed desiredTotal wins.
• Each number can only be picked once (no reuse).
• Return true if the first player can guarantee a win, false otherwise.

Thought Process

At first glance, the problem seems to require checking all possible sequences of moves, which grows exponentially as the number of choices increases. A brute-force approach would try every possible pick for each player at every turn, but this quickly becomes infeasible for larger inputs.

The key insight is to recognize that the game's state can be represented by the set of unused numbers and the current total. If we know which numbers are left and what the target is, the rest of the game is deterministic. This allows us to use memoization (caching) to avoid recomputing the same situations. We also realize that if the sum of all available numbers is less than the desiredTotal, it is impossible for any player to win, so we can return false immediately.

Instead of thinking in terms of all possible move sequences, we can reframe the problem as: "Can the current player force a win from this state?" We recursively check if there's any move that leaves the opponent in a losing position.

Solution Approach

To solve the problem efficiently, we use recursion with memoization. The main steps are:

1. Early Checks:
   • If the sum of all numbers from 1 to maxChoosableInteger is less than desiredTotal, return false immediately.
   • If desiredTotal is 0 or less, the first player wins by default.
2. State Representation:
   • Represent the set of used numbers as a bitmask (an integer where each bit indicates if a number is used). This allows us to efficiently store and look up game states.
3. Recursive Function:
   • For each unused number, simulate picking it and check if the opponent can win from the resulting state.
   • If there is any pick that forces the opponent to lose, the current player can win.
4. Memoization:
   • Store the result for each unique state (bitmask) to avoid recalculating it.
5. Base Case:
   • If picking a number makes the total reach or exceed desiredTotal, the current player wins.

This approach ensures that each unique state is only computed once, making the solution efficient even for larger inputs.

Example Walkthrough

Let's walk through an example with maxChoosableInteger = 4 and desiredTotal = 6.

• First Player's Turn:
  • Can pick 1, 2, 3, or 4.
  • If picks 4: total is 4. Opponent can pick 3, total is 7 (opponent wins), so not safe.
  • If picks 3: total is 3. Opponent can pick 4 (total 7, opponent wins), so not safe.
  • If picks 2: total is 2. Opponent can pick 4 (total 6, opponent wins immediately), so not safe.
  • If picks 1: total is 1. Opponent can pick 4 (total 5), then first player can pick 3 (total 8, first player wins). But opponent might pick 3 instead, so we must check all branches.
• Recursive Exploration:
  • The function explores all possible picks and their consequences, caching results for repeated states.
  • Eventually, it finds that with optimal play, the first player cannot guarantee a win in this setup.

This step-by-step analysis is handled efficiently by recursion and memoization in the code.

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(N!) where N is maxChoosableInteger, since each move branches to all unused numbers.
  • Space Complexity: O(N!), storing all possible game states.
• Optimized (Memoized) Approach:
  • Time Complexity: O(2^N * N). There are 2^N possible bitmask states, and for each state, we try up to N choices.
  • Space Complexity: O(2^N), for the memoization cache.

This is efficient for N up to 20, which is the constraint in the original problem.

Summary

The "Can I Win" problem is an example of recursive game theory with memoization. By representing the state as a bitmask and caching results, we avoid redundant calculations and efficiently determine if the first player can force a win. The key insights are recognizing the game's state structure and using memoization to optimize the search space. This approach transforms an exponential-time brute-force problem into a manageable solution, making it both elegant and practical.

Code Implementation

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= 0:
            return True
        total_sum = (maxChoosableInteger * (maxChoosableInteger + 1)) // 2
        if total_sum < desiredTotal:
            return False

        memo = {}

        def can_win(used, curr_total):
            if used in memo:
                return memo[used]
            for i in range(1, maxChoosableInteger + 1):
                if not (used >> (i-1)) & 1:
                    if curr_total + i >= desiredTotal:
                        memo[used] = True
                        return True
                    if not can_win(used | (1 << (i-1)), curr_total + i):
                        memo[used] = True
                        return True
            memo[used] = False
            return False

        return can_win(0, 0)
      

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        int totalSum = (maxChoosableInteger + 1) * maxChoosableInteger / 2;
        if (totalSum < desiredTotal) return false;

        unordered_map<int, bool> memo;

        function<bool(int, int)> canWin = [&](int used, int currTotal) {
            if (memo.count(used)) return memo[used];
            for (int i = 1; i <= maxChoosableInteger; ++i) {
                if (!(used & (1 << (i - 1)))) {
                    if (currTotal + i >= desiredTotal) {
                        memo[used] = true;
                        return true;
                    }
                    if (!canWin(used | (1 << (i - 1)), currTotal + i)) {
                        memo[used] = true;
                        return true;
                    }
                }
            }
            memo[used] = false;
            return false;
        };

        return canWin(0, 0);
    }
};
      

import java.util.*;

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        int totalSum = (maxChoosableInteger + 1) * maxChoosableInteger / 2;
        if (totalSum < desiredTotal) return false;

        Map<Integer, Boolean> memo = new HashMap<>();

        return canWin(0, 0, maxChoosableInteger, desiredTotal, memo);
    }

    private boolean canWin(int used, int currTotal, int maxChoosable, int target, Map<Integer, Boolean> memo) {
        if (memo.containsKey(used)) return memo.get(used);
        for (int i = 1; i <= maxChoosable; i++) {
            if ((used & (1 << (i - 1))) == 0) {
                if (currTotal + i >= target) {
                    memo.put(used, true);
                    return true;
                }
                if (!canWin(used | (1 << (i - 1)), currTotal + i, maxChoosable, target, memo)) {
                    memo.put(used, true);
                    return true;
                }
            }
        }
        memo.put(used, false);
        return false;
    }
}
      

var canIWin = function(maxChoosableInteger, desiredTotal) {
    if (desiredTotal <= 0) return true;
    let totalSum = (maxChoosableInteger + 1) * maxChoosableInteger / 2;
    if (totalSum < desiredTotal) return false;

    const memo = new Map();

    function canWin(used, currTotal) {
        if (memo.has(used)) return memo.get(used);
        for (let i = 1; i <= maxChoosableInteger; i++) {
            if (((used >> (i - 1)) & 1) === 0) {
                if (currTotal + i >= desiredTotal) {
                    memo.set(used, true);
                    return true;
                }
                if (!canWin(used | (1 << (i - 1)), currTotal + i)) {
                    memo.set(used, true);
                    return true;
                }
            }
        }
        memo.set(used, false);
        return false;
    }

    return canWin(0, 0);
};