The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
public IList<int> GrayCode(int n) { IList<int> res = new List<int>(){0}; var visited = new HashSet<int>(); visited.Add(0); return BackTracking(n,res,visited,0); } private IList<int> BackTracking(int n, IList<int> res, HashSet<int> visited, int cur ) { if(res.Count() >=Math.Pow(2,n)) { return res; } else { for(int i =0;i<n;i++) { int compare = 1 << i; int a = cur ^ compare; var temp = visited; if(visited.Add(a)) { res.Add(a); var b = BackTracking(n,res,visited,a); if(b != null) return b; res.RemoveAt(res.Count()-1); } visited = temp; } } return null; }
原文：http://www.cnblogs.com/renyualbert/p/5877855.html