89. Gray Code

using System.Threading;
public class Solution {
    private List<int> result;
    private HashSet<int> isPresent;
    public List<int> GrayCode(int n) {
        result = new List<int> { 0 };
        isPresent = new HashSet<int> { 0 };
        Thread thread = new Thread(() => GrayCodeHelper(0, n), 1024 * 1024 * 10);
        thread.Start();
        thread.Join();
        return result;
    }
    private bool GrayCodeHelper(int current, int n) {
        if (result.Count == (1 << n))
            return true;
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (!isPresent.Contains(next)) {
                isPresent.Add(next);
                result.Add(next);
                if (GrayCodeHelper(next, n))
                    return true;
                isPresent.Remove(next);
                result.RemoveAt(result.Count - 1);
            }
        }
        return false;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private List<int> result;
    private HashSet<int> isPresent;
    public List<int> GrayCode(int n) {
        result = new List<int> { 0 };
        isPresent = new HashSet<int> { 0 };
        Thread thread = new Thread(() => GrayCodeHelper(0, n), 1024 * 1024 * 10);
        thread.Start();
        thread.Join();
        return result;
    }
    private bool GrayCodeHelper(int current, int n) {
        if (result.size() == (1 << n))
            return true;
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (!isPresent.Contains(next)) {
                isPresent.push_back(next);
                result.push_back(next);
                if (GrayCodeHelper(next, n))
                    return true;
                isPresent.Remove(next);
                result.RemoveAt(result.size() - 1);
            }
        }
        return false;
    }
}

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        Set<Integer> isPresent = new HashSet<>();
        isPresent.add(0);
        grayCodeHelper(result, n, isPresent);
        return result;
    }

    private boolean grayCodeHelper(
        List<Integer> result,
        int n,
        Set<Integer> isPresent
    ) {
        if (result.size() == (1 << n)) return true;

        int current = result.get(result.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (!isPresent.contains(next)) {
                isPresent.add(next);
                result.add(next);
                if (grayCodeHelper(result, n, isPresent)) return true;
                isPresent.remove(next);
                result.remove(result.size() - 1);
            }
        }
        return false;
    }
}

var grayCode = function (n) {
    const res = [0];
    const seen = new Set(res);
    const helper = (n, res, seen) => {
        if (res.length === Math.pow(2, n)) {
            return true;
        }
        const curr = res[res.length - 1];
        for (let i = 0; i < n; i++) {
            const next = curr ^ (1 << i);
            if (!seen.has(next)) {
                seen.add(next);
                res.push(next);
                if (helper(n, res, seen)) return true;
                seen.delete(next);
                res.pop();
            }
        }
        return false;
    };
    helper(n, res, seen);
    return res;
};

class Solution:
    def grayCode(self, n: int):
        result = [0]
        isPresent = {0}
        self.grayCodeHelper(result, n, isPresent)
        return result

    def grayCodeHelper(self, result, n, isPresent):
        if len(result) == (1 << n):
            return True
        current = result[-1]
        for i in range(n):
            nextNum = current ^ (1 << i)
            if nextNum not in isPresent:
                isPresent.add(nextNum)
                result.append(nextNum)
                if self.grayCodeHelper(result, n, isPresent):
                    return True
                isPresent.remove(nextNum)
                result.pop()
        return False

func grayCode(n int) []int {
    seen := map[int]bool{0: true}
    res := []int{0}
    var helper func(n int, seen map[int]bool) bool
    helper = func(n int, seen map[int]bool) bool {
        if len(res) == 1<<n {
            return true
        }
        curr := res[len(res)-1]
        for i := 0; i < n; i++ {
            next := curr ^ (1 << i)
            if seen[next] == false {
                seen[next] = true
                res = append(res, next)
                if helper(n, seen) {
                    return true
                }
                seen[next] = false
                res = res[:len(res)-1]
            }
        }
        return false
    }
    helper(n, seen)
    return res
}

Explanation

Algorithm

1️⃣

Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0.

2️⃣

Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения.

Начните с числа 0.

В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов.

3️⃣

Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent.

Продолжайте поиск с next.

Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения.

Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск.

При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true.

Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false.

😎