ciw

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

class Solution {
public:
    bool canIWin(int maxInt, int total) {
        if(total < maxInt)
            return true;

        if ((maxInt + 1)*maxInt/2 < total)
            return false;

        vector <int> numUsed (maxInt + 1);
        fill(numUsed.begin(), numUsed.end(), 0);
        this->maxInt = maxInt;
        map <vector <int>, bool> memory;
        return makeTurn(numUsed, total, memory);
    }

private:
    int maxInt;

    bool makeTurn(vector <int> &used, int total, map <vector <int>, bool> &memory) {
        bool ret = false;

        auto it = memory.find(used);
        if (it != memory.end()) {
            return it->second;
        }

        if (total <= 0) {
            return false;
        }

        for (int i = 1; i <= maxInt; i++) {
            if (used[i])
                continue;

            used[i] = 1;

            ret = !makeTurn(used, total - i, memory);

            used[i] = 0;

            if(ret)
               break;
        }
        memory.insert(pair<vector<int>, bool>(used, ret));
        return ret;
    }

};