[InterviewBit] Gray Code

Gray Code

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
unordered_set<int> vis;
bool helper(vector<int>& res, int sz, int len) {
if(res.size() == sz) return true;
else {
for(int i = 0; i < len; i++) {
int mask = res.back() ^ (1<<i);
if(vis.count(mask)) continue;
res.push_back(mask);
vis.insert(mask);
if(helper(res,sz,len)) return true;
res.pop_back();
vis.erase(mask);
}
return false;
}
}
vector<int> Solution::grayCode(int A) {
vector<int> res {0};
vis.clear();
vis.insert(0);
helper(res, pow(2,A), A);
return res;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/22/PS/interviewbit/gray-code/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.