Leetcode: Gray Code

This question is asked both at Amazon and Microsoft. Here it is: 

An n-bit gray code sequence is a sequence of 2^n integers where:

Every integer is in the inclusive range of [0, 2^n - 1]. First integer is 0 and an integer appears no more than once in the sequence. Binary representation of first and last integer as well as adjacent integers differs by one bit. 

Input: n = 2

Output: [0,1,3,2]

Explanation:

The binary representation of [0,1,3,2] is [00,01,11,10].

- 00 and 01 differ by one bit

- 01 and 11 differ by one bit

- 11 and 10 differ by one bit

- 10 and 00 differ by one bit

[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].

- 00 and 10 differ by one bit

- 10 and 11 differ by one bit

- 11 and 01 differ by one bit

- 01 and 00 differ by one bit

[0, 2, 3, 1] is also valid sequence, whose binary representation is [00, 01, 11, 10].

So we have return a valid n gray code sequence. where n is the number of digits. 

We are going to solve these by backtracking. We need to check out all of the possibilities that are not part of the current sequence. 

So we need to try values out and backtrack whenever we don't have other values. 

We first initialize a result to store the solution sequence, and add 0 to the list before calling the helper method. Why? All of the gray code sequences start with 0. 

If the grayCodeHelper find each possible number by toggling the ith bit of the number. 

If next is not present add it to the result list and isPresent set. If next is not present in the set of numbers add it to the result list. 

Now the Hashmap can be represented by an unordered set. 

class Solution {

    public: 

        vector<int> grayCode(int n) {

            //initializer a result vector to return

            vector<int> result; 

            //append 0 to result. all gray code starts with 0. 

            result.push_back(0);

            //hash map or unordered set to see if the number is present. 

            unordered_set<int> isPresent;

            //0 is always present so we can push this to the set. 

            isPresent.insert(0); 

            //call the helper function

            grayCodeHelper(result, n, isPresent);

            return result;

        }

    private: 

        bool grayCodeHelper(vector<int> &result, int n, unordered_set<int> &isPresent) {

            //base case see if full size already 

            if(result.size() == (1 << n)) {

                return true;

            }

            //get last element of the result and try each adjacent element and see if it is present. 

            int current = result[result.size() - 1]; 

            for(int i = 0; i < n; i++) {

                //perform a mod-or operation on this on the ith digit. 

                //if is not present, insert this vaue

                if(isPresent.find(next) == isPresent.end()) {

                    isPresent.insert(next);

                    result.push_back(next);

                    //call recursive method to return true

                    if(grayCodeHelper(result, n, isPresent)) { 

                        return true;

                    }

                    isPresent.erase(next); //else if element exists already delete if there is no valid sequence and continue search.

                result.pop_back();

                }    

            }

            return false;

        }

};

So basically in a nutshell, we check base case get 0, iterate through all the possible bits and recursively call the grey hope helper and backtrack any solution that returns false.