Java solution use backtracking


  • -2
    X

    backtracking: g(n) = [g(n-1), reverse(g(n-1))+2^n-1 ];
    base case: n==0 : return [0].

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> res=new LinkedList<Integer>();
            
            if(n==0){//base case
                res.add(0);
            }else{
                List<Integer> list1=grayCode(n-1);
                List<Integer> list2=new LinkedList<Integer>();
                for(int i:list1){
                    list2.add(i+(int)Math.pow(2,n-1));
                }
                Collections.reverse(list2);
                
                res.addAll(list1);
                res.addAll(list2);
            }
            return res;
            
        }
    }

  • 0
    C

    It's just simple recursion, not backtracking. see here for backtracking solution.


Log in to reply
 

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