Backtracking solution


  • 3
    R
    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> result = new ArrayList<Integer>();
            List<Integer> list = new ArrayList<Integer>();
            list.add(0);
            helper(result,list,n);
            return result;
        }
        public void helper(List<Integer> result,List<Integer> list,int n){
            
            if(list.size() == Math.pow(2,n)){
                result.addAll(list);
                return;
            }
            int last = list.get(list.size() - 1);
            
            for(int i = 0; i < n; i++){
                int off = 1 << i;
                int cur = last ^ off;
                
                if(list.contains(cur)) continue;
                
                list.add(cur);
                helper(result,list,n);
                
                if(result.size() > 0) return;
                list.remove(list.size() - 1);
            }
            
        } 
    }
    }
    

    Using backtracking without knowing gray code knowledge. Find one solution and return.


Log in to reply
 

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