C++ Memorized DFS Solution 350ms


  • 0
    J
    class Solution {
    public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if (desiredTotal <= 0) return true;
            if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false;
            
            unordered_map<int, bool> memo;
            unsigned int used = 0;
            return CanYouWin(memo, used, desiredTotal, maxChoosableInteger);
        }
        
        bool CanYouWin(unordered_map<int, bool>& memo, unsigned int& used, int desiredTotal, int& maxChoosableInteger) {
            
            // if other player reaches the total then u lose
            if (desiredTotal <= 0) return false;
            
            if (memo.find(used) != memo.end()) return memo[used];
            
            unsigned int old = used;
            
            for (int i = 1; i <= maxChoosableInteger; i++) {
                
                if (!((1 << i) & used)) {
                    used |= (1 << i);
                    // if i picked some number, can the other player can not win
                    if (!CanYouWin(memo, used, desiredTotal - i, maxChoosableInteger)) {
                        memo[old] = true;
                        used = old;
                        return true;
                    }
                    
                     used = old;
                }
                
            }
            
            memo[old] = false;
            return false;
            
        }
    };
    

Log in to reply
 

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