Leetcode 464 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);
    }
};