LeetCode 464 Can I Win - Implementation

You're building a recursive function with memoization. The state is a bitmask representing which numbers have been picked. The base case checks if the player can win immediately by picking any remaining number.

For the recursive case, you try each unpicked number. If picking that number makes the opponent lose, you win. Otherwise, keep trying other numbers. The memoization key is the bitmask itself.

Since there are $2^{20}$ possible states and you visit each once, the solution runs in $O(2^n \cdot n)$ time. You'll cache results in a map where the key is the integer value of the bitmask. This is a classic minimax game theory problem: you win if there exists a move that makes your opponent lose.

Time: $O(2^n \cdot n)$. Space complexity: $O(2^n)$ with bitmask memoization.