# Ac solution code

• Solution1. Simplified - Special thanks to @yuyibestman

This is an iterative solution: Add prefix '1' to the previous sequence (from the last one). Because the the previous sequence should differ 1 bit between the successive two numbers, so if we add prefix '1' to them, they should still differ 1 bit between the successive two numbers.

``````     There're two parts for sequence(i+1):
n = 2:  00(1),   01(2),   11(3),    10(4)
=>   n = 3: 000(1),  001(2)   011(3)    010(4) - PART1
n = 3: 110(4),  111(3)   101(2)    100(1) - PART2
PART1: Same as sequence(i);
PART2: Add prefix '1' to the sequence(i) (from the last one).
``````

JAVA Code:

``````public List<Integer> grayCode(int n) {
for (int i = 0; i < n; i++) {
int size = res.size();
for (int j = size - 1; j >= 0; j--) {// Add prefix '1' to the previous sequence (from the last one)
}
}
return res;
}
``````

Solution2. DFS

The basic idea is using DFS to change 1 bit of the last visited number each time. It's a bit more complex than solution1, but it can output all possible sequences if we want. So, still worth a shot ;)
Changing 1 bit part is messed up, didn't figure out how to change 1 bit concisely, any advice would be appreciated!

JAVA Code:

``````public List<Integer> grayCode(int n) {
DFS(n, res);
return res;
}
boolean DFS(int n, List<Integer> res) {
if (res.size() == 1 << n) return true;
int last = res.get(res.size() - 1);
for (int i = 0; i < n; i++) {
int cur = 0;
// change 1 bit
int bitI = (last >> i) & 1;
if (bitI == 1) cur = last - (1 << i);
else cur = last + (1 << i);

if (!res.contains(cur)) {