Skip to content

464. Can I Win 👍

  • Time: $O(n \codt turns)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0)
      return true;

    const int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (sum < desiredTotal)
      return false;

    return dp(desiredTotal, 0, maxChoosableInteger);
  }

 private:
  unordered_map<int, bool> memo;  // true: can win, false: can't win

  // state: record integers that have been chosen
  bool dp(int total, int state, int n) {
    if (total <= 0)
      return false;
    if (const auto it = memo.find(state); it != cend(memo))
      return it->second;

    for (int i = 1; i <= n; ++i) {
      if (state & 1 << i)  // Integer i is used
        continue;
      if (!dp(total - i, state | 1 << i, n))
        return true;
    }

    return memo[state] = false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0)
      return true;

    final int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (sum < desiredTotal)
      return false;

    return dp(desiredTotal, 0, maxChoosableInteger);
  }

  // true: can win, false: can't win
  private Map<Integer, Boolean> memo = new HashMap<>();

  // state: record integers that have been chosen
  private boolean dp(int total, int state, int n) {
    if (total <= 0)
      return false;
    if (memo.containsKey(state))
      return memo.get(state);

    for (int i = 1; i <= n; ++i) {
      if ((state & 1 << i) == 1) // Integer i is used
        continue;
      if (!dp(total - i, state | 1 << i, n))
        return true;
    }

    memo.put(state, false);
    return false;
  }
}