simple solution with backtracking


  • 0
    E
    public List<Integer> grayCode(int n) {
            List<Integer> integers = new ArrayList<>();
            if (n==0) {
                integers.add(0);
                return integers;
            }
            if (n==1) {
                integers.add(0);
                integers.add(1);
                return integers;
            }
            byte[] arr = new byte[n];
            grayCode(arr, n-1, integers, n);
            return integers;
        }
    
        public void grayCode(byte arr[], int ptr, List<Integer> list, int n) {
            if (ptr==1) {
                if (arr[1] == 0) {
                    list.add(byteToInt(arr, n));
                    arr[0] = 1;
                    list.add(byteToInt(arr, n));
                    arr[1] = 1;
                    list.add(byteToInt(arr, n));
                    arr[0] = 0;
                    list.add(byteToInt(arr, n));
                } else {
                    list.add(byteToInt(arr, n));
                    arr[0] = 1;
                    list.add(byteToInt(arr, n));
                    arr[1] = 0;
                    list.add(byteToInt(arr, n));
                    arr[0] = 0;
                    list.add(byteToInt(arr, n));
                }
            } else {
                grayCode(arr, ptr-1, list, n);
                arr[ptr] = (byte) (arr[ptr] == 0 ? 1 : 0);
                grayCode(arr, ptr-1, list, n);
            }
    
        }
    
        int byteToInt(byte[] arr, int n) {
            int res = 0;
            for (int i = n-1; i >= 0; i--) {
                byte b = arr[i];
                if (b == 0) {
                    res = res<<1;
                } else {
                    res = res<<1|1;
                }
            }
            return res;
        }
    

Log in to reply
 

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