# Backtracking C++ solution

• ``````class Solution {
void utils(bitset<32>& bits, vector<int>& result, int k){
if (k==0) {
result.push_back(bits.to_ulong());
}
else {
utils(bits, result, k-1);
bits.flip(k-1);
utils(bits, result, k-1);
}
}
public:
vector<int> grayCode(int n) {
bitset<32> bits;
vector<int> result;
utils(bits, result, n);
return result;
}
};``````

• Hi, it is a brilliant idea! Just wanna know why it is backtracking?

• Great idea!!! Based on your idea I implement in JAVA

``````    int nums = 0;
public List<Integer> grayCode(int n) {
List<Integer> ret = new ArrayList<>();
backTrack(n, ret);
return ret;
}

private void backTrack(int n, List<Integer> ret) {
if (n == 0) {
return;
}
else {
backTrack(n - 1, ret);
nums ^= (1 << n - 1);
backTrack(n - 1, ret);
}
}
``````

• Modified @zhidou's java code to carry num instead of member field.

``````public List<Integer> grayCode(int n) {
List<Integer> ans = new ArrayList<>();
Integer num = 0;
dfs(ans, num, n);
return ans;
}

//    private void dfs(List<Integer> ans, int nums, int k) {

/**
* DFS solution with known property:  num ^ ((1 << level) - 1)
* @param ans
* @param num: Note, must use Integer or int[1] to carry the reference
* @param k
*/
private void dfs(List<Integer> ans, Integer num, int k) {
if (k == 0) {