Gray Code Problem
Description
LeetCode Problem 89.
An n-bit gray code sequence is a sequence of 2^n integers where:
- Every integer is in the inclusive range [0, 2^n - 1],
- The first integer is 0,
- An integer appears no more than once in the sequence,
- The binary representation of every pair of adjacent integers differs by exactly one bit, and
- The binary representation of the first and last integers differs by exactly one bit.
Given an integer n, return any valid n-bit gray code sequence.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit
Example 2:
1
2
Input: n = 1
Output: [0,1]
Constraints:
- 1 <= n <= 16
Sample C++ Code
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
30
31
class Solution {
public:
vector<int> ans;
int toDecimal(vector<int>& bin) {
int dec = 0;
for (int i = 0; i < bin.size(); i ++) {
dec = (dec << 1) + bin[i];
}
return dec;
}
void backtrack(vector<int>& candidates, int idx) {
if (idx == -1) {
ans.push_back(toDecimal(candidates));
return;
}
backtrack(candidates, idx-1);
candidates[idx] = 1 - candidates[idx];
backtrack(candidates, idx-1);
}
vector<int> grayCode(int n) {
vector<int> candidates(n, 0);
backtrack(candidates, n-1);
return ans;
}
};