1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public List<Integer> grayCode(int n) {
List<Integer> ans = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
ans.add(0);
visited.add(0);
backtrack(0, n, visited, ans);
return ans;
}
private boolean backtrack(int lastElement, int n, Set<Integer> visited, List<Integer> ans) {
if (ans.size() == Math.pow(2, n)) {
return true;
}
for (int i = 0; i < n; i++) {
int currElement = ans.size() == Math.pow(2, n) - 1 ? ans.get(0) ^ (1 << i) : lastElement ^ (1 << i);
if (!visited.contains(currElement)) {
visited.add(currElement);
ans.add(currElement);
if (backtrack(currElement, n, visited, ans)) {
return true;
}
visited.remove(currElement);
ans.remove(ans.size() - 1);
}
}
return false;
}
}
|
