464. Can I Win

MediumBit ManipulationMemoizationMathDynamic ProgrammingBitmaskGame Theory

Problem Description

In this leetcode problem, the "100 game" is used as an example of a two-player game where the players alternate turns, adding an integer from a specified range to a cumulative total. The objective of the game is to be the player who makes the running total reach or exceed a target value, known as the desiredTotal. The twist in this version of the game is that once a number has been used, it cannot be used again (without replacement). The task is to determine whether the first player can guarantee a win given complete access to the entire pool of numbers from 1 to the maxChoosableInteger and assuming both players make the most optimal move available to them at each turn. The problem asks to return true if the first player can ensure a victory and false otherwise.

Intuition

To determine if the first player has a winning strategy, we need a way to evaluate all possible game states without re-evaluating positions multiple times. We can use recursion to simulate each player's turns, where each state represents a unique combination of remaining numbers and the current total.

The state of the game is tracked using a bitmap where bits represent whether a particular number has been chosen already. Starting from an initial state where no numbers have been chosen and the current total is 0, we explore all possible moves for the first player, recursively simulating the opponent's response to each move.

If we can find any move such that the resulting state either:

Reaches/exceeds the desiredTotal—immediately winning the game, or
Forces the opponent into a position where they cannot win (every subsequent move leads to a loss),

then the first player can guarantee a win.

However, a naive recursive approach could re-compute the same state multiple times. To avoid this, we use memoization to cache the results of subproblems, which ensures each unique game state is only computed once. This is done using the @cache decorator in the Python code.

The base condition to end the recursion is reaching a state where the current total is greater than or equal to the desiredTotal, or if there are no moves left that could prevent the opponent from winning on their next turn. If no winning strategy is found for any possible move, the function returns false, indicating the first player cannot guarantee a win.

Before starting the recursive approach, there's an initial check to see if the sum of all choosable integers is less than the desiredTotal. If so, it's impossible for either player to reach the target score, and the function immediately returns false.

Learn more about Memoization, Math, Dynamic Programming and Bitmask patterns.

Solution Approach

The implementation of the solution employs a Depth-First Search (DFS) algorithm combined with memoization. The DFS algorithm explores all possible game moves recursively, while memoization is used to cache results of previously encountered game states to avoid recalculations.

Here's a step-by-step explanation of the solution approach:

State Representation: We use an integer (state) to represent the current state of the game, where each bit in state indicates whether a number has been chosen. If the i-th bit is set, the number i has already been selected.
Recursion with DFS: The dfs(state, t) function is the heart of the DFS approach, where state represents the current game state and t the current sum. For each call of dfs, we loop through all integers from 1 to maxChoosableInteger to simulate choosing a new number.
Checking Valid Moves: For each potential move, we check if the corresponding bit in state is not set, meaning the number hasn't been used yet. (state >> i) & 1 does this check.
Winning Conditions: Upon choosing a number i, we add it to the current sum t. If this new sum t + i is greater than or equal to desiredTotal, we found a winning move. Alternatively, if the recursive call dfs(state | 1 << i, t + i) returns false, it means the opponent cannot win after we make this move, so it's also a winning move for us.
End of Recursion: If none of the moves lead to a winning situation, the function will eventually return false, indicating that with optimal play from the opponent, the first player cannot win from this specific state.
Memoization: We use the @cache decorator on the dfs function to cache the results. Whenever the dfs function is called with a state that has been computed before, it will return the cached result instead of recalculating.
Initial Check: Before invoking the DFS, we calculate the sum s of all numbers that could be chosen. If s is less than desiredTotal, it's impossible for either player to reach the target, and the function immediately returns false.
Return Statement: Finally, if the initial sum check passes, the function returns the result of the initial dfs(0, 0), signifying whether the first player has a winning strategy starting from an empty state with a sum of 0.

Mathematically, the memoization ensures that the time complexity of the algorithm is reduced to O(2^n), where n is maxChoosableInteger, because we only need to compute each of the 2^n possible states once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the "100 game" example and walk through a smaller case to understand the solution approach. Assume the desiredTotal is 10 and the maxChoosableInteger is 6. This means each player can choose from integers 1 to 6 without replacement to reach or exceed the total of 10.

Initial Check: We calculate the sum of all numbers from 1 to 6, which is 1+2+3+4+5+6=21. Since 21 is greater than 10, it's possible to reach the desired total, so we proceed with the DFS approach.
First Recursive Call: We call dfs(0, 0) because initially, no numbers have been chosen (state is 0) and the running total (t) is also 0.
Exploring Moves: The first player begins by exploring all numbers from 1 to 6:
- If Player 1 chooses 1, the state changes to 000001 (1 << (1 - 1)), and t becomes 1. The function then calls dfs(000001, 1).
- If Player 1 chooses 2, the state becomes 000010 and t becomes 2, leading to a call of dfs(000010, 2).
- This process continues until all possible first moves are explored.
Recursing Deeper: Let's consider Player 1 had chosen 1.
- Now it’s Player 2's turn with state 000001 and total 1. Player 2 also explores moves 2 through 6.
- If Player 2 chooses 2 next, the state becomes 000011 (000001 | 1 << (2 - 1)) and t becomes 3. The function then calls dfs(000011, 3).
Checking Winning Condition: Assume Player 1 plays 1, then Player 2 plays 2, and Player 1 follows with 6 on the next turn. Now, the state is 000011 for 1 and 2 being used, and the running total is 1+2+6 = 9.
- On the next turn, if there exists any number that Player 1 can choose that results in a total of 10 or more, Player 1 will win. Player 1 can choose 1 which results in a total of 10. Since dfs for this state returns true, Player 1 has a winning strategy.
Memoization: If at any point, the dfs function encounters a state that it has seen before, instead of recomputing, it will use the cached result. This dramatically reduces the number of computations needed.
Conclusion: Using the DFS and memoization, we evaluate all possible sequences of moves. If Player 1 has a guaranteed strategy to reach or exceed the desired total of 10, dfs(0, 0) will ultimately return true. If each recursive branch eventually leads to a state where Player 1 cannot win, the function will return false.

For our small example, an optimal strategy exists for Player 1 to win by choosing the sequence 1, 6, and 3 (or several other combinations), resulting in reaching the desiredTotal of 10. So, the output for dfs(0, 0) would be true, indicating Player 1 can guarantee a win.

Solution Implementation

1from functools import lru_cache  # Import the lru_cache decorator for memoization
2
3class Solution:
4    def canIWin(self, max_choosable_integer: int, desired_total: int) -> bool:
5        # Use memoization to store results of subproblems and avoid recomputation
6        @lru_cache(maxsize=None)
7        def can_win_game(state: int, current_total: int) -> bool:
8            # Iterate through all possible integers that can be chosen
9            for integer in range(1, max_choosable_integer + 1):
10                # Check if 'integer' has already been chosen in the 'state'
11                if (state >> integer) & 1:
12                    continue  # Skip this iteration as 'integer' is already taken
13                # Check if choosing 'integer' now would win the game, or the opponent cannot win after we choose 'integer'
14                if current_total + integer >= desired_total or not can_win_game(state | (1 << integer), current_total + integer):
15                    return True  # Current player can win by choosing 'integer'
16            return False  # No winning move found; current player loses
17
18        # Compute the sum of all integers that can be chosen
19        sum_of_integers = (1 + max_choosable_integer) * max_choosable_integer // 2
20        # If the sum is less than the desired total, no one can win
21        if sum_of_integers < desired_total:
22            return False
23
24        # Start the game with the initial state (all zeros) and total 0
25        return can_win_game(0, 0)
26
27# Example of using the code:
28# Create a Solution object
29solution = Solution()
30
31# Set the maximum choosable integer and desired total
32max_choosable_integer = 10
33desired_total = 11
34
35# Call the canIWin method and print the result
36result = solution.canIWin(max_choosable_integer, desired_total)
37print("Can I win?", result)
38

1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5    // A memoization map to store previously computed results for given states
6    private Map<Integer, Boolean> memo = new HashMap<>();
7
8    // Main method to determine if the player can win given the max number and desired total
9    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
10        // Calculate the sum of all choosable integers
11        int sumOfAllIntegers = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
12      
13        // If the sum is less than the desired total, no one can win
14        if (sumOfAllIntegers < desiredTotal) {
15            return false;
16        }
17      
18        // Start the depth-first search to determine if the player can win
19        return depthFirstSearch(0, 0, maxChoosableInteger, desiredTotal);
20    }
21
22    // Helper method for depth-first search
23    private boolean depthFirstSearch(int usedNumbersState, int currentTotal, int maxChoosableInteger, int desiredTotal) {
24        // Check if the state has already been computed
25        if (memo.containsKey(usedNumbersState)) {
26            return memo.get(usedNumbersState);
27        }
28      
29        // By default, assume the player cannot win with the current state
30        boolean canWin = false;
31      
32        // Loop through all choosable integers
33        for (int i = 1; i <= maxChoosableInteger; ++i) {
34            // Check if the number has not been chosen yet (bit is not set)
35            if (((usedNumbersState >> i) & 1) == 0) {
36                // If choosing number i reaches or exceeds desiredTotal or the opponent cannot win,
37                // it means the current player can win.
38                if (currentTotal + i >= desiredTotal
39                    || !depthFirstSearch(usedNumbersState | (1 << i), currentTotal + i, maxChoosableInteger, desiredTotal)) {
40                    canWin = true;
41                    break;  // Terminate the loop as we found a winning situation
42                }
43            }
44        }
45      
46        // Store the computed result in the memo map before returning it
47        memo.put(usedNumbersState, canWin);
48        return canWin;
49    }
50}
51

1#include <unordered_map>
2using namespace std;
3
4class Solution {
5public:
6    // Determines if the current player can win the game.
7    bool canIWin(int maxChoosableInteger, int desiredTotal) {
8        // Calculate sum of all choosable integers
9        int sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
10        // Check if the sum is less than the desired total, which means no one can win
11        if (sum < desiredTotal) return false;
12
13        // Prepare a memoization table to store intermediate results
14        unordered_map<int, bool> memo;
15      
16        // Call to the recursive function to determine if we can win
17        return dfs(0, 0, maxChoosableInteger, desiredTotal, memo);
18    }
19
20private:
21    // Recursive function to check if we can reach the desired total from the current state.
22    bool dfs(int state, int currentTotal, int maxChoosableInteger, int desiredTotal, unordered_map<int, bool>& memo) {
23        // Check if the current state has been computed before
24        if (memo.count(state)) return memo[state];
25
26        // Initialize the result as false
27        bool result = false;
28      
29        // Try every choosable integer to see if we can win
30        for (int i = 1; i <= maxChoosableInteger; ++i) {
31            // Skip if i is already used in the current state
32            if ((state >> i) & 1) continue;
33
34            // If adding i to currentTotal meets or exceeds desiredTotal, or the opponent cannot win,
35            // set the result as true and break (current player wins)
36            if (currentTotal + i >= desiredTotal || !dfs(state | (1 << i), currentTotal + i, maxChoosableInteger, desiredTotal, memo)) {
37                result = true;
38                break;
39            }
40        }
41
42        // Memoize and return the result for the current state
43        memo[state] = result;
44        return result;
45    }
46};
47

1// Importing the necessary utilities from 'collections' module
2import { HashMap } from 'collectable';
3
4// Global memoization table to store intermediate results
5const memo: HashMap<number, boolean> = new HashMap<number, boolean>();
6
7// Determines if the current player can win the game given the max choosable integer and the desired total
8const canIWin = (maxChoosableInteger: number, desiredTotal: number): boolean => {
9    // Calculate sum of all choosable integers to check if winning is possible
10    const sum: number = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
11    // No one can win if the sum is less than the desired total
12    if (sum < desiredTotal) return false;
13
14    // Call to the recursive function to determine if the current player can win
15    return dfs(0, 0, maxChoosableInteger, desiredTotal);
16};
17
18// Recursive function to check if the current player can reach the desired total from the current state
19const dfs = (state: number, currentTotal: number, maxChoosableInteger: number, desiredTotal: number): boolean => {
20    // Check for an existing computation for the current state
21    if (memo.has(state)) return memo.get(state)!;
22
23    // Initialize the result as false
24    let result = false;
25
26    // Iterate through every choosable integer to find a winning move
27    for (let i = 1; i <= maxChoosableInteger; ++i) {
28        // Check if 'i' has been used in the current state
29        if ((state >> i) & 1) continue;
30
31        // Check if adding 'i' to currentTotal wins the game, or if the opponent cannot win on the next turn
32        if (currentTotal + i >= desiredTotal || !dfs(state | (1 << i), currentTotal + i, maxChoosableInteger, desiredTotal)) {
33            result = true;
34            break; // Current player wins, so we break the loop
35        }
36    }
37
38    // Save the result to the memoization table for the current state
39    memo.set(state, result);
40
41    // Return the computed result
42    return result;
43};
44```
45
46The TypeScript code provided does not include a direct equivalent for `unordered_map` from C++ which is used for memoization; instead, I've used `HashMap` from the 'collectable' library which is a TypeScript-compatible library providing persistent immutable data structures. If `collectable` is not preferred, you may use a regular JavaScript `Map` object or a plain object with some adjustments to the hashing strategy for the state.
47
48To use TypeScript's `Map` object instead:
49
50```typescript
51// Replace the import statement with the following line
52const memo = new Map<number, boolean>();
53// and replace each HashMap method as follows:
54// memo.has(state) -> memo.has(state)
55// memo.get(state)! -> memo.get(state)!
56// memo.set(state, result) -> memo.set(state, result)
57

Time and Space Complexity

Time Complexity

The time complexity of the canIWin function is dependent on two factors: the number of recursive calls made by the dfs(state, t) function and the number of iterations within each call.

Each state in the dfs function represents a unique combination of chosen integers and can be represented by a bitmask, where the integer i is chosen if the i-th bit is set to 1. There are 2^maxChoosableInteger possible states because each of the maxChoosableInteger integers can be either chosen or not chosen.

For each call of dfs, we iterate from 1 to maxChoosableInteger to try all possibilities, which gives us O(maxChoosableInteger) for each call.

However, we don't visit all possible states of dfs due to the game ending once the desiredTotal is reached or exceeded. Plus, memoization using cache ensures that we only compute each state once.

Considering this, the worst-case time complexity is O(maxChoosableInteger * 2^maxChoosableInteger) since there are maxChoosableInteger operations done in each of the 2^maxChoosableInteger possible states.

Space Complexity

The space complexity is governed by the cache used to store the results for each state and the stack space used by the recursion.

Cache: Storage for each unique state requires O(2^maxChoosableInteger) space as there are that many possible states.
Recursion Stack: In the worst case, the recursion can go as deep as maxChoosableInteger levels if we continue to choose a new number until we run out, which is O(maxChoosableInteger) space.

Hence, the overall space complexity is also O(maxChoosableInteger + 2^maxChoosableInteger), which simplifies to O(2^maxChoosableInteger) as the exponential term dominates the linear term.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know