Simple recursion solution with explantion


  • 0

    There are many way to generate Gray Code and Gray Code is not unique. Here is a recursion solution.

    we list out 2bits Gray Code

    00

    01

    11

    10

    then list out 3bits Gray Code

    000

    001

    011

    010

    110

    111

    101

    100

    we will find that 3bits Gray Code can generate from 2bits Gray Code.

    The first four 3bits Gray Code can generate by add 0 before 2bits Gray Code from the first to the last.

    The last four 3bits Gray Code can generate by add 1 before 2bits Gray Code from the last to the first.

    So we can do this in recursion.

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

Log in to reply
 

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