Clear Explanation and also Java code attached


  • 1

    Just observe:

    n=1
    
    0
    1
    
    n=2
    
    00
    01
    ---  now comes 2nd with 1
    11  (=10 + 01) 
    10  (=10 + 00)
    
    n=3
    
    000
    001
    ---- now comes 2nd with 1
    011  (=010 + 001) 
    010  (=010 + 000) 
    ---- now comes 3rd with 1
    110  (=100 + 010) 
    111  (=100 + 011)
    101  (=100 + 001)
    100  (=100 + 000)
    

    So it seems the gray code is formed by "prefix + the reverse of previous sequence"
    Now the Java code can solve this easily:

    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        if(n==0)
            return res;
        if(n==1) {
            res.add(1);
            return res;
        }
        int prefix = 1<<(n-1);
        res = grayCode(n-1);
        for(int i=res.size()-1; i>=0; i--)
            res.add(prefix+res.get(i));
        return res;
    }

Log in to reply
 

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