464. Can I Win
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 instate
indicates whether a number has been chosen. If thei
-th bit is set, the numberi
has already been selected. -
Recursion with DFS: The
dfs(state, t)
function is the heart of the DFS approach, wherestate
represents the current game state andt
the current sum. For each call ofdfs
, we loop through all integers from1
tomaxChoosableInteger
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 sumt
. If this new sumt + i
is greater than or equal todesiredTotal
, we found a winning move. Alternatively, if the recursive calldfs(state | 1 << i, t + i)
returnsfalse
, 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 thedfs
function to cache the results. Whenever thedfs
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. Ifs
is less thandesiredTotal
, it's impossible for either player to reach the target, and the function immediately returnsfalse
. -
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 EvaluatorExample 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
to6
, which is1+2+3+4+5+6=21
. Since21
is greater than10
, 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
is0
) and the running total (t
) is also0
. -
Exploring Moves: The first player begins by exploring all numbers from
1
to6
:- If Player 1 chooses
1
, the state changes to000001
(1
<< (1 - 1)), andt
becomes1
. The function then callsdfs(000001, 1)
. - If Player 1 chooses
2
, the state becomes000010
andt
becomes2
, leading to a call ofdfs(000010, 2)
. - This process continues until all possible first moves are explored.
- If Player 1 chooses
-
Recursing Deeper: Let's consider Player 1 had chosen
1
.- Now itās Player 2's turn with state
000001
and total1
. Player 2 also explores moves2
through6
. - If Player 2 chooses
2
next, the state becomes000011
(000001
|1
<< (2 - 1)) andt
becomes3
. The function then callsdfs(000011, 3)
.
- Now itās Player 2's turn with state
-
Checking Winning Condition: Assume Player 1 plays
1
, then Player 2 plays2
, and Player 1 follows with6
on the next turn. Now, the state is000011
for1
and2
being used, and the running total is1+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 choose1
which results in a total of10
. Sincedfs
for this state returnstrue
, Player 1 has a winning strategy.
- On the next turn, if there exists any number that Player 1 can choose that results in a total of
-
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 returntrue
. If each recursive branch eventually leads to a state where Player 1 cannot win, the function will returnfalse
.
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 isO(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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!