Problem 464

Abstract / Summary

Given target points and a list of numbers, decide if you can reach exactly the target by adding numbers without reusing any.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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)
32 lines | 1185 bytes | submitted September 29, 2023 | GitHub   29% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.81 | σ = 1.25

Complexity Analysis

Time: exponential
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
34 links | 20 authors | 10 languages

Videos

3 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

10 solutions   September 29, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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