LeetCode Weekly Contest 160, Problem 2

Non-recursive.cpp

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        stack<int> stk; // search stack (open set). Use (-1) to represent a traceback
        vector<int> currVec; // current state of partial permutation
        unordered_set<int> currSet; // records integers in currVec
        stk.push(start);
        while (!stk.empty()) {
            int curr = stk.top(); // pop the current value
            stk.pop();
            if (curr < 0) { // trace back mark
                currSet.erase(currVec.back());
                currVec.pop_back();
            }
            currVec.push_back(curr); // append current value to the permutation
            currSet.insert(curr);
            //
            if (currVec.size() == (1 << n)) { // permutation complete
                int x = currVec.back() ^ start;
                for (int i = 0; i < n; i++) if (x == (1 << i)) return currVec;
                currSet.erase(currVec.back()); // trace back if not valid
                currVec.pop_back();
            }
            //
            stk.push(-1); // put traceback mark
            for (int i = 0; i < n; i++) {
                int x = currVec.back() ^ (1 << i); // push next possible values into open set
                if (currSet.find(x) == currSet.end()) {
                    stk.push(x);
                }
            }
        }
        return currVec;
    }
};

Recursive.cpp

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> currVec; // current state of partial permutation
        unordered_set<int> currSet; // records integers in currVec
        currVec.push_back(start);
        currSet.insert(start);
        solve(n, start, currVec, currSet); // returns true immediately after any final state is reached
        return currVec;
    }

private:
    static bool solve(int n, int start, vector<int>& currStk, unordered_set<int>& currSet) {
        if (currStk.size() == (1 << n)) { // permutation complete (length reaches 2^n)
            int x = currStk.back() ^ start;
            for (int i = 0; i < n; i++) if (x == (1 << i)) return true;
            return false;
        }
        for (int i = 0; i < n; i++) {
            int x = currStk.back() ^ (1 << i); // next possible value
            if (currSet.find(x) == currSet.end()) {
                currStk.push_back(x);
                currSet.insert(x);
                if (solve(n, start, currStk, currSet)) {
                    return true;
                }
                currStk.pop_back();
                currSet.erase(x);
            }
        }
        return false;
    }
};