Gray Code

• Time : $O(A^(2^A))$
• Space : $O(2^A)$

c++

unordered_set<int> vis;
bool helper(vector<int>& res, int sz, int len) {
    if(res.size() == sz) return true;
    else {
        for(int i = 0; i < len; i++) {
            int mask = res.back() ^ (1<<i);
            if(vis.count(mask)) continue;
            res.push_back(mask);
            vis.insert(mask);
            if(helper(res,sz,len)) return true;
            res.pop_back();
            vis.erase(mask);
        }
        return false;
    }
}
vector<int> Solution::grayCode(int A) {
    vector<int> res {0};
    vis.clear();
    vis.insert(0);
    helper(res, pow(2,A), A);
    return res;
}