Description of the Java solution


  • 0
    L

    If you look at the result set, you will find that doing it with backtracking requires special checks making it difficult doing that way. I see there are plenty of solutions that use bit manipulations. This solution recognizes the pattern that the first half of the bits generated by a number can be pre-pended with '0' first and then '1' in the reverse order.

        public List<Integer> grayCode(int n) {
            if(n==0) {
                return Arrays.asList(0);
            }
            List<String> grays = helper(n);
            List<Integer> list = new ArrayList<>(grays.size());
            for(String s : grays) {
                list.add(Integer.valueOf(s,2));
            }
            return list;
        }
        
        private List<String> helper(int n) {
             if(n==1) {
                 return Arrays.asList("0","1");
             }    
         
             List<String> list = helper(n-1);
             //Half will start with '0' and the 
             List<String> newlist = new ArrayList<>();
             for(int i = 0 ; i<list.size();i++) {
                 newlist.add('0'+list.get(i));
             }
             for(int i = list.size()-1;i>=0;i--) {
                 newlist.add('1'+list.get(i));    
             }
            return newlist;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.