# brute force and memoization

1. O(n!) brute force, n is maxChoosableInteger. T(n)=nT(n-1)
``````    bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(!desiredTotal) return 1;
return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal);
}
bool canWin(int pool, int maxint, int tot) {
if(tot<=0) return 0;
for(int i=0;i<maxint;i++) {
if(!canWin(pool,maxint, tot-i-1)) return 1;
}
return 0;
}
``````
1. O(n2^n) Memoization. There is redundant computation in #1. A state with a pool and total may be computed many times. So we can cache the state and reuse it. At first glance, it seems that a state is determined by two values, the pool and the total. However, since the initial total is known, the remaining total is known given the pool. So a state can be identified by the pool only.
``````    bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(!desiredTotal) return 1;
if(maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return 0;
unordered_map<int,char> mem;
return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal, mem);
}
bool canWin(int pool, int maxint, int tot, unordered_map<int,char>& mem) {
if(tot<=0) return 0;
auto it = mem.find(pool);
if(it != mem.end()) return it->second;
for(int i=0;i<maxint;i++) {
}
return mem[pool] = 0;
}
``````
1. Iterative dp. For most dp problems, the next step is to transform recursion with memoization to iterative dp. However, that does not help and is actually pretty bad for this problem. In iterative dp, we have to visit all the 2^n states to get the result. In #2 DFS with memoization, DFS terminates as soon as it finds a way to win. The worst case O(n2^n) rarely happens. So if DFS has early termination condition, then it should be better than dp that visits all the states. Similar problems are word break and Concatenated Words.

• @yu6
Could please explain the condition if(tot<=0) return 0; in canWin function.
if tot == 0 return 0; seems fine. But if tot<0 why the function is returning "0".

According to the problem description, the player who first causes the running total to reach or exceed the desiredTotal wins. If a player sees negative total in his turn, it means the other player causes the running total to exceed the desiredTotal in the previous move and wins.

• Thank you for sharing. I simplified a little bit.

``````class Solution {
bool canWin(int pool, int maxint, int tot, unordered_map<int, bool>& memo) {
if(tot <= 0) return false;
auto it = memo.find(pool);
if (it != memo.end()) return it->second;
for(int i = 1; i <= maxint; i++) {
if(!canWin(pool | mask, maxint, tot-i, memo)) {
return memo[pool] = true;
}
}
return memo[pool] = false;
}
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(desiredTotal == 0) return true;
if(maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal) return false;
unordered_map<int, bool> memo;
return canWin(0, maxChoosableInteger, desiredTotal, memo);
}
``````

• This post is deleted!

• @yu6
From a pool of numbers as we have 2 players they need to select numbers taking turns ,so i added a playerflag .
if playerflag is true that means it is is player1 turn and we are looking for his win.
In the code I check if desiredTotal reaches 0 and playerflag== true.
Why does this code not work,What did I misunderstand?

``````#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool canWin(int pool, int maxint, int tot, bool flag);

bool canIWin(int maxChoosableInteger, int desiredTotal)
{
if(!desiredTotal) return 1;
return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal, false);
}

bool canWin(int pool, int maxint, int tot, bool playerflag)
{

if(tot<=0 && playerflag == false)
{
return false;
}
else if(tot <= 0 && playerflag == true)
{

return true;
}

(playerflag)?playerflag = false:playerflag = true;

for(int i=0;i<maxint;i++)
{

bool flag = canWin(pool,maxint, tot-i-1, playerflag);
if(flag)
{
return true;
}
}

return false;
}
``````

• @skocharl My solution does not need the player flag, canWin just means if a player can win given the pool and total. Adding the player flag makes it more complicated. canWin() becomes if player 1 can win given the pool, total can starting player.

``````    bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(!desiredTotal) return 1;
return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal,1);
}
bool canWin(int pool, int maxint, int tot, bool player) {
if(tot<=0) return !player;
for(int i=0;i<maxint;i++) {
bool canP1win = canWin(pool,maxint, tot-i-1,!player);
if(player && canP1win) return 1;
if(!player && !canP1win) return 0;
}
return !player;
}
``````

• @yu6 Hi yu6 I have a question about the time complexity.

I understand why you mean time complexity is 2^n, but my question is even we already store all the visited state, for the worst case, we still need to check all (for(int i=0;i<maxint;i++)) to get the current state, right? Specifically for each visited state we can use O(1) to check but for the worst case, we need to check N visited state, which totally will be O(N), right?

Then why is the time complexity not n*(2^n).

Thanks

• @aken848_3 thanks for your correction. Update my post.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.