89. Gray Code

Description

The problem is to generate the sequence of Gray codes for a given number n. A Gray code sequence is a sequence of 2^n integers where the binary representation of each integer differs from the previous one by exactly one bit. The sequence starts with 0 and must include all 2^n numbers exactly once.

Intuition

The key idea behind generating Gray codes is to ensure that each successive number in the sequence differs from the previous one by only one bit. This can be achieved by flipping one bit at a time, starting from the least significant bit. By tracking which numbers have already been visited, we can ensure that the sequence is valid and contains all the necessary numbers.

Approach

1. Initialization: Start with the initial number 0 and mark it as visited.
2. Backtracking: Recursively try to generate the next number by flipping one bit at a time. If the next number hasn't been visited, add it to the result and continue the process.
3. Termination: The recursion terminates when all 2^n numbers have been added to the result.
4. Backtrack if necessary: If a certain path does not lead to a complete solution, backtrack by removing the last number and trying the next possible bit flip.

Complexity

Time Complexity:

The time complexity is O(2^n * n). This is because there are 2^n numbers in the sequence, and for each number, we may need to explore up to n possible next steps.

Space Complexity:

The space complexity is O(2^n) for storing the sequence and the set of visited numbers.

Code

C++

class Solution {
public:
    std::vector grayCode(int n) {
        std::vector result = {0};
        std::unordered_set visited = {0};

        std::function generateGrayCode = [&](int num) {
            if (result.size() == pow(2, n)) return true;
            for (int i = 0; i < n; i++) {
                int next = num ^ (1 << i);

                if (visited.find(next) == visited.end()) {
                    result.push_back(next);
                    visited.insert(next);

                    if (generateGrayCode(next)) return true;

                    result.pop_back();
                    visited.erase(next);
                }
            }
            return false;
        };

        generateGrayCode(0);
        return result;
    }
};

Python

class Solution:
    def grayCode(self, n: int) -> list[int]:
        result = [0]
        visited = set([0])

        def generateGrayCode(num):
            if len(result) == 2 ** n:
                return True
            for i in range(n):
                next_num = num ^ (1 << i)

                if next_num not in visited:
                    result.append(next_num)
                    visited.add(next_num)

                    if generateGrayCode(next_num):
                        return True

                    result.pop()
                    visited.remove(next_num)
            return False

        generateGrayCode(0)
        return result

Java

class Solution {
    public List grayCode(int n) {
        List result = new ArrayList<>();
        result.add(0);
        Set visited = new HashSet<>();
        visited.add(0);

        if (generateGrayCode(0, n, result, visited)) {
            return result;
        }
        return result;
    }

    private boolean generateGrayCode(int num, int n, List result, Set visited) {
        if (result.size() == (1 << n)) return true;
        for (int i = 0; i < n; i++) {
            int next = num ^ (1 << i);

            if (!visited.contains(next)) {
                result.add(next);
                visited.add(next);

                if (generateGrayCode(next, n, result, visited)) return true;

                result.remove(result.size() - 1);
                visited.remove(next);
            }
        }
        return false;
    }
}

JavaScript

var grayCode = function (n) {
    const result = [0];
    const generateGrayCode = (num, visited) => {
        if (result.length === Math.pow(2, n)) return true;
        for (let i = 0; i < n; i++) {
            const next = num ^ (1 << i);

            if (!visited.has(next)) {
                result.push(next);
                visited.add(next);

                if (generateGrayCode(next, visited)) return true;

                result.pop();
                visited.delete(next);
            }
        }
        return false;
    };
    generateGrayCode(0, new Set([0]));

    return result;
};