It is easy to identify that this problem can be solved using recursion by considering each available choice for both players. We will need a visited array which stores the numbers already chosen. For each number not yet chosen, choose that number and see if the outcome comes in favor of the player.
The solution will give TLE without memoization and the trick lies there. We want to store for each unique visited array the outcome (true or false). The length of our visited array will be equal to maxChoosableInteger as it stores for each number 1…maxChoosableInteger, whether we have visited it or not. So we want to make a map of [1…maxChoosableInteger] -> outcome. We can’t use hash table for this as the key is not allowed to be an array in any language. The most intuitive way of doing this is to convert the array into comma-separated string and store the outcome but unfortunately this gives TLE in C++.
There’s a very interesting way to use just an integer instead of the string as key for the map (hash table). Notice that maxChoosableInteger is given to be <= 20. 2^21 comes in the range of an int in C++ so what if we can bitmask the array visited[1…maxChoosableInteger]? It means that, let us define an integer key which will have 1 in its binary if visited[i] is 1 else it will be 0. To store [1…maxChoosableInteger], we need the key’s binary equivalent length to be 21 (as it is 0-indexed). A binary having length 21 can store maximum 2^21 value so we can store it in an int. Consider an example of visited array:
visited = [1, 0, 1, 1, 0]
1 2 3 4 5
So our binary would be 010110 (we consider binary to be 0-indexed so first digit will always be 0)
Integer equivalent is 26
Below code uses this memoization technique:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
// sanity check
if (desiredTotal<=maxChoosableInteger)
return true;
// sum of first n numbers is n*(n+1)/2
if (desiredTotal>(maxChoosableInteger*(maxChoosableInteger+1))/2)
return false;
unordered_map<int, bool> memo;
vector<bool> vis(maxChoosableInteger+1, false);
return helper(desiredTotal, memo, vis);
}
bool helper (int desiredTotal, unordered_map<int, bool>& memo, vector<bool>& vis) {
if (desiredTotal<=0)
return false;
int key = 0;
for (int i=1; i<vis.size(); i++)
key += vis[i] ? 1<<i : 0;
if (memo.find(key) != memo.end())
return memo[key];
for (int i=1; i<vis.size(); i++) {
if (!vis[i]) {
vis[i] = 1;
if (!helper(desiredTotal-i, memo, vis)) {
memo[key] = true;
vis[i]=0;
return memo[key];
}
vis[i] = 0;
}
}
memo[key] = false;
return memo[key];
}
It is interesting to notice that we can even bitmask the visited array. The key for the map (hash table) defined above has its i-th bit = 1 if visited[i] is true. We can get the i-th bit of the key using key&1<<i and use it to check if i-th number is visited or not!
bool canIWin(int maxChoosableInteger, int desiredTotal) {
// sanity check
if (desiredTotal<=maxChoosableInteger)
return true;
if (desiredTotal>(maxChoosableInteger*(maxChoosableInteger+1))/2)
return false;
unordered_map<int, bool> memo;
return helper(desiredTotal, memo, 0, maxChoosableInteger);
}
bool helper (int desiredTotal, unordered_map<int, bool>& memo, int key, int& M) {
if (desiredTotal<=0)
return false;
if (memo.find(key) != memo.end())
return memo[key];
for (int i=1; i<=M; i++) {
if (!(key&1<<i) && !helper(desiredTotal-i, memo, key|1<<i, M)) {
memo[key] = true;
return memo[key];
}
}
memo[key] = false;
return memo[key];
}