Can I win ? Dynamic Programming , Bitmask Easy Approach Explanation #leetcode #leetcodesolution

Hi Everyone ,
Please Support My channel do like share and subscribe to my Channel
I will bring more content like this

Please Connect With Me:

#leetcode #leetcodesolution #leetcodequestions #xor #contest #gfg #coding

[aryanbarnwal]

I have a doubt why don't we need to memoize T or the number left here as well? It is also a state which is changing with every recursive call. Please help.

[HimankKalal-yj]

We can restate the orignal problem as:
Does there exist a choice for the 1st player, that no matter what choice the 2nd player make later, the 1st player always has a path to win?

This restatement explains why the dfs funciton is designed as what it is in this solution.
The return value of function dfs means:

true: there exists a choice which can make current player win
false: there does not exists any choice which can make current player win
The the following ideas are natural:

For-loop all choices (i.e. choose any valid num at each step), and return true immediately if we already find a path for 1st player to win.
If we have for-loop all choices and could not find any path for 1st player to win, we return false.
Then I give some explanations to the code itself.

M: (int) maxChoosableInteger

T: (int) desiredTotal

T-(i+1): (int) temp total, which is subtracted from the original desiredTotal by the picking i th number [1, maxChooseableInteger]

k: (int) the i-th bit of k (base 2) records whether the i-th num is picked by players

dp: (dp, size -20( as we have at max 20 maxChooseableInteger)) m[k] records the return value of dfs under the state of pick k

k&(1<<i): (bool): checks if number is already choosed or not.

true: i-th bit of k is 1, which means i-th num has been picked by one player
false: i-th bit of k is 0, which means i-th num has not been picked by any player
k|(1<<i): (int): Update k after pick i-th num

dfs(M, T, k):

true: there exists a choice for 1st player to have a path to win
false: there does not exist any choice for 1st player to have a path to win
dft(M, T-i, k):

true: there exists a choice for 2nd player to have a path to win if 1st player pick i-th num
false: there does not exist any choice for 2nd player to have a path to win if 1st player pick i-th num

[soumyajitmishra]

Thanks for the video I am little bit experienced so I could able to catch this but for a beginner your explanation is not at all perfect you told i will try to make you understand bit mask in best way but you did not even make an attempt to make others understand So you need to improve.

[devarajm]

Correction, You are saying a player can choose any number from 0 to MaxChoosableInteger but that is not the case. A player can choose any number from 1 to MaxChoosableInteger.

[RajatSingh-vswu]

The state T is also changing so why haven't we considered that in the dp array?

[Omneeshkushwah]

I am unable to understand this question

[lakshsinghania]

sir i didnt undertstand your explanation its bit unclear

[soumalyadhar.]

dont make videos... first learn to explain things to others