Description Link to heading

464. Can I Win (Medium)

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.

Example 1:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Example 2:

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3:

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

Constraints:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

Solution Link to heading

dfs Link to heading

First, let’s think in dfs, if the first player chooses x, for the next player, the desiredTotal becomes desiredTotal - x, and if the second player wins, the first player loses.

bitmask + memorized search Link to heading

Since maxChoosableInteger <= 20, we can use a bit number mask to show the process of choosing numbers. If the ith digit of mask is 1, it means that number i hasn’t been chosen;

And we should note that the value of desired_total entirely depends on mask, so the cache vector is cache[mask], not cache[mask][desired_total].

Note the priority of the bit operation, the brackets are required.

Code Link to heading 

class Solution {
  public:
    bool dfs(int desired_total, int cur_total, int bit20, int max_int, unordered_map<int, int> &ump) {
        if (desired_total <= 0) {
            return false;
        }
        if (bit20 == 0) {
            return true;
        }
        if (ump.find(bit20) != ump.end()) {
            return ump[bit20];
        }
        bool tmp = false;
        int cnt = 1;
        for (int i = max_int - 1; i >= 0; --i) {
            if ((bit20 & (1 << i)) != 0) { // it means `i + 1` hasn't been chosen
                int mask = (bit20 ^ (1 << i));
                tmp = tmp || (!dfs(desired_total - i - 1, cur_total + i + 1, mask, max_int, ump));
            }
            if (tmp) {
                ump[bit20] = true;
                return ump[bit20];
            }
        }
        ump[bit20] = false;
        return ump[bit20];
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= maxChoosableInteger) {
            return true;
        }
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        unordered_map<int, int> ump;
        int bit20 = (1 << maxChoosableInteger) - 1;
        return dfs(desiredTotal, 0, bit20, maxChoosableInteger, ump);
    }
};