Leetcode 464 Solution

This article provides solution to leetcode question 464 (can-i-win)
Categories:
Tags:
Access this page by simply typing in "lcs 464" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/can-i-win

Solution

class Solution {
    unordered_map<int64_t, bool> m_cache;



public:
    int64_t getKey(int total, int used)
    {
        return (((int64_t)total) << 32) + used;
    }



    bool canIWin(int desiredTotal, int maxChoosableInteger, int used)
    {
        int64_t key = getKey(desiredTotal, used);



        if (m_cache.find(key) != m_cache.end())
            return m_cache[key];



        for (int i = 1; i <= maxChoosableInteger; i++)
        {
            if ((used & (1 << i)) == 0)
            {
                if (i >= desiredTotal || canIWin(desiredTotal - i, maxChoosableInteger, used | (1 << i)) == false)
                    return m_cache[key] = true;
            }
        }



        return m_cache[key] = false;
    }



    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal)
            return false;



        int used = 0;
        return canIWin(desiredTotal, maxChoosableInteger, used);
    }
};