Typical backtracking solution without using bit manipulation


  • 0
    B

    This problem is very similar with permutation pronblem. so we can use DFS and backtracking to solve this problem.But the gray code is binary numeral system where two successive values differ in only one bit, so we need to reverse the array which store 0 and 1, when we add 1 to list which store the binary numbers. When the list's size equal n , convert binary to deciamal and add deciamal to result.

    `

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> result = new ArrayList<>();
            List<Integer> grayCode = new ArrayList<>();
            // if (n == 0) {
            //     return result;
            // }
            int[] a = {0, 1};
            solver(result, grayCode, a, n);
            return result;
        }
        public void solver (List<Integer> result, List<Integer> grayCode, int[] a, int n) {
            if (grayCode.size() == n) {
                double sum = 0;
                for (int i = 0 ; i < grayCode.size(); i++) {
                    if (grayCode.get(i) == 1) {
                        sum += Math.pow(2, grayCode.size() - 1 - i);
                    }
                }
                result.add((int)sum);
                return;
            }
            for (int i = 0 ; i < 2; i++) {
                grayCode.add(a[i]);
                if (a[i] == 0) {
                    solver(result, grayCode, a, n);
                } else {
                    swap(a);
                    solver(result, grayCode, a, n);
                    swap(a);
                }
                grayCode.remove(grayCode.size() - 1);
            }
        }
        public void swap (int[] a) {
            int temp = a[0];
            a[0] = a[1];
            a[1] = temp;
        }
    }`

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.