464. Can I Win

[namespace-io]

class Solution {
public:
    int dfs(int M, int T, unordered_map<int, bool>& m, int k){
        if(T <= 0) return false;
        if(m.count(k) != 0) return m[k];
        for(int i = 1; i <= M; i++){
            if(!(k & (1 << i) ) && !dfs(M, T - i, m, k | (1 << i))) {
                m[k] = true;
                return m[k];
            }
        }
        m[k] = false;
        return m[k];
    }
    bool canIWin(int M, int T) {
       
        if((M+1) * M / 2 < T ) return false;
        unordered_map<int, bool> m;
        return M >= T ? true : dfs(M, T, m, 0);
    }
};