JAVA-----------Easy Version To Understand!!!!!!

• ``````public static List<Integer> grayCode(int n) {
if (n < 0)
return new ArrayList<Integer>();
if (n == 0) {
List<Integer> list = new ArrayList<Integer>();
return list;
}
List<Integer> tmp = grayCode(n - 1);
List<Integer> result = new ArrayList<Integer>(tmp);
int addNumber = 1 << (n - 1);
for (int i = tmp.size() - 1; i >= 0; i--) {
}

return result;
}``````

• Not so easy to understand...Can you explain it?

• Look at the examples, you will find out they are symmetric if the first bit is cut off .

n = 1

0

1

n=2

0 0

0 1

1 1

1 0

n=3

0 0 0

0 0 1

0 1 1

0 1 0

1 1 0

1 1 1

1 0 1

1 0 0

• I try to explain a little bit...

``````n = 0: 0
n = 1: 0, 1
n = 2: 00, 01, 11, 10  (0, 1, 3, 2)
n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)
``````

Take n=3 as the example, the first four sequences are exactly same as n=2 sequences.
The second four sequences are derived of the following steps:

1. reverse n=3 first half sequence: 010, 011, 001, 000
2. Add 2^2 to each element of reversed n=2 sequence

Now we can extend to n=i situation.
The first half of n=i is the same sequence as n=i-1
The second half of n=i is add 2^(i-1) to the reversed sequence of first half.

• This post is deleted!

• C++ Equivalent code

``````class Solution {
vector<int> result;
public:
vector<int> grayCode(int n) {
vector<int> result;
if(n<0) return result;
if(n==0) {result.push_back(0); return result;}
result = grayCode(n-1);
//cout<<result.size();
int x=1<<n-1;
for(int i=result.size()-1;i>=0;i--) {
result.push_back(x+result[i]);
}
return result;
}
};
``````

• I come up with a similar solution, and it's more concise. Please check it out.

``````/*
n = 0: 0
n = 1: 0 | 1
n = 2: 00, 01 | 11, 10
n = 3: 000, 001, 011, 010 | 110, 111, 101, 100
f(n) = f(n - 1) | 2 ^ (n - 1) + f(n - 1)
*/
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();

for(int i = 1; i <= n; i++) {
int size = res.size(), base = 1 << (i - 1);
for(int j = size - 1; j >= 0; j--) {
}
}
return res;
}
}
``````

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