MEDIUM Backtracking / Memoization

464. Can I Win

📖 Problem

In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100. Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise return false. Assume both players play optimally.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Recursive stack flow
  • •Cycle prevention
  • •Post-order reasoning

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply DFS reasoning pattern
  • •Apply Backtracking reasoning pattern
  • •Apply Recursion reasoning pattern

💡 Approach

  • → Use memoization with bitmask to track used numbers
  • → Recursively try each available number
  • → If current player can make opponent lose, current player wins
  • → If sum of all numbers < desiredTotal, impossible to win
  • → Time: O(2^n), Space: O(2^n) for memo

🛠️ Hints & Pitfalls

Hints

  • •Use memoization with bitmask to track used numbers
  • •Recursively try each available number
  • •If current player can make opponent lose, current player wins

Common Pitfalls

  • •If sum of all numbers < desiredTotal, impossible to win
  • •Time: O(2^n), Space: O(2^n) for memo

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
canIWin(10, 11);
Expected:
true
Test Case 2
Not run
Input:
canIWin(4, 6);
Expected:
true
Test Case 3
Not run
Input:
canIWin(5, 5);
Expected:
true

📝 Code Editor

📚 Reference Solution

▼
⌘K Search ⌘↩ Run ⌘S Submit