Python 0464.py
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
@cache
def deeper(available): # bitmask
used = 0
high = 0
for i in range(maxChoosableInteger):
value = i + 1 # zero-based masks
if available & (1 << i):
high = value
else:
used += value
if used + high >= desiredTotal:
return True
# if opponent can't win, then we win
for i in range(maxChoosableInteger):
if available & (1 << i):
without = available & ~(1 << i) # clear bit
if not deeper(without):
return True
# all paths are forced wins for the opponent
return False
# stupid test case with an undefined edge case: not enough numbers for anyone to win
total = maxChoosableInteger * (maxChoosableInteger + 1) // 2 # triangle number
if total < desiredTotal:
return False
return deeper((1 << maxChoosableInteger) - 1)
Difficulty
and has an acceptance rate of about 31% (300k+ submissions).
Typical patterns to solve this problem:
- Bit Manipulation
- Bitmask
- Dynamic Programming
- Game Theory
- Math
- Memoization
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the “Can I Win” combinatorial game problem. Two players alternately pick distinct integers from 1 to maxChoosableInteger. The first player whose cumulative sum reaches or exceeds desiredTotal wins. The algorithm determines whether the starting player has a forced win assuming optimal play from both sides.
The solution builds a recursive search over the set of remaining numbers, encoded as a bitmask. Memoization via @cache eliminates repeated evaluation of identical game states. An early-exit test based on the total sum of all numbers handles the trivial impossible case. Within the recursion, a quick win check using the largest available number and the sum of already taken numbers prunes the search space before exploring deeper moves.
Key Steps
1. Pre-check for an impossible target
Before any recursion begins, the code computes the triangular sum of all selectable integers. If this sum is smaller than desiredTotal, no sequence of moves can ever reach the target, and the function returns False immediately.
total = maxChoosableInteger * (maxChoosableInteger + 1) // 2
if total < desiredTotal:
return False
2. Representation of game state
The recursive helper deeper receives a single integer available whose binary representation indicates which numbers are still selectable. Bit i (zero-based) corresponds to the integer i + 1. A set bit means the number is still available; a cleared bit means it has already been chosen.
3. Memoized recursive exploration
The @cache decorator stores the result of each distinct available mask. When the same mask reappears, the cached Boolean is returned instantly, preventing exponential blow-up.
@cache
def deeper(available):
...
4. Deriving used sum and highest remaining value
Inside deeper, a loop iterates over all possible indices. For each index, the code distinguishes between a taken number (bit cleared) and a still-available number (bit set). The variable used accumulates the sum of numbers that have already been taken, while high tracks the largest value that remains available.
used = 0
high = 0
for i in range(maxChoosableInteger):
value = i + 1
if available & (1 << i):
high = value
else:
used += value
5. Immediate win detection
If the sum of all numbers already taken (used) plus the largest still-available number (high) reaches or exceeds desiredTotal, the current player can win on this turn by selecting high. The function returns True without further recursion.
if used + high >= desiredTotal:
return True
6. Exploring opponent-forcing moves
When an instant win is not available, the algorithm tries each possible move. For every set bit in available, it clears that bit to form the next state without. It then calls deeper recursively. If any recursive call returns False, it means the opponent cannot force a win from that resulting state, so the current player can secure a victory by choosing that move. The function returns True as soon as such a move is found.
for i in range(maxChoosableInteger):
if available & (1 << i):
without = available & ~(1 << i)
if not deeper(without):
return True
7. Exhausted search leads to loss
If the loop finishes without finding a move that leaves the opponent without a winning response, every possible continuation results in a win for the opponent. Consequently, the current player loses, and the function returns False.
return False
8. Initiating the recursion with a full mask
The initial call to deeper supplies a mask where all bits up to maxChoosableInteger are set, indicating that every number is initially available.
return deeper((1 << maxChoosableInteger) - 1)
Edge Cases Handled
The algorithm explicitly addresses the scenario where the total sum of all numbers is insufficient to meet desiredTotal. This early exit prevents unnecessary recursion for inputs that are mathematically unwinnable.
Within the recursive routine, the condition used + high >= desiredTotal captures the case where the current player can clinch the game by picking the largest remaining number, even when the exact target has not yet been reached. This covers situations where the cumulative sum is just shy of the target and a single high value can push it over.
The bitmask approach naturally handles the situation where no numbers remain (mask equals zero). In that case, the loop over possible moves does not execute, and the function falls through to the final return False, correctly indicating that the player to move cannot win because no moves exist.
Performance Optimizations
Memoization via @cache is the primary optimization, collapsing the exponential game tree into a manageable number of distinct states. Because each state is uniquely identified by a bitmask of length maxChoosableInteger, the total number of cached entries is bounded by 2^{maxChoosableInteger}. The cache ensures that each state is evaluated at most once.
Encoding the set of available numbers as a bitmask yields constant-time checks and updates using bitwise operations. The loop that computes used and high runs in linear time with respect to maxChoosableInteger, but it avoids constructing auxiliary data structures such as lists or sets, keeping memory overhead low.
The early win detection (used + high >= desiredTotal) eliminates deep recursion in many branches where a winning move is obvious, cutting off exploration before the full depth of the game tree is reached.
Finally, the initial total-sum check prevents the recursive engine from being invoked when the problem is provably unsolvable, saving both time and memory for those inputs.
ELI5 - Simplified Explanation
Imagine a game where a group of number cards lies face up on a table. Each number has a different value, and players take turns picking one card to add to a running score. The goal is to be the person who finally makes the score reach or pass a specific target number.
This code acts like an expert player who thinks ahead to see if a win is possible. First, the code checks if there are even enough cards to reach the target at all. If the sum of all the cards is too small, nobody can win, so the game stops immediately.
When it becomes a player's turn, the code looks at all the cards still waiting on the table. It imagines picking each one by one to see what happens next. The trick is to look at the game from the other player's perspective. If the code can pick a card that forces the other player into a situation where they have no way to win, then the code knows it has made a perfect move.
The computer uses a clever way to keep track of which cards are still left. It turns the list of cards into a tiny secret code of ones and zeros, which lets it remember every single state of the game it has already studied. By looking at all these possibilities, the code figures out if the starting player has a strategy that leads to a victory regardless of how the other player decides to play.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||||
| WalkCCC | C++ | Java | Python | ||||||||
| leetcode.ca | C++ | Java | Python | Go | TS | ||||||
| LeetcodeHelp | C++ | Java | Python | ||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||
| Progiez | C++ | Java | Python | ||||||||
| github | black-shadows | C++ | |||||||||
| charles-wangkai | Java | ||||||||||
| everthis | JS | ||||||||||
| gouthampradhan | Java | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| yuanliu666 | Kotlin | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| everthis | JavaScript | ||||||||||
| gouthampradhan | Java | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| yuanliu666 | Kotlin |
Videos
Similar Problems
- problem 375: Guess Number Higher or Lower II
- problem 486: Predict the Winner
Solved On The Same Day
- problem 729: My Calendar I
- problem 1286: Iterator for Combination
- problem 1348: Tweet Counts Per Frequency
- problem 1387: Sort Integers by The Power Value
- problem 2424: Longest Uploaded Prefix
- problem 327: Count of Range Sum
- problem 699: Falling Squares
- problem 1553: Minimum Number of Days to Eat N Oranges
- problem 1611: Minimum One Bit Operations to Make Integers Zero
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality