Loop Formula Solution - Gray Code

The idea is that first assume n - 1 case exists, and then add it as 0 +, as for 1 +, the formula is to add 1 to each from pre result and add at the opposite order…

The second solution is to use bit manipulation. First add elements to a pre processing list, which contains finalResult.size - 1 elements, by adding symmetric and middle.
Then add 0 case to final result, and process the pre processing list by bit operation. Notice that process last element by current index added in pre processing list… guarantee the neighbors are next to each other.

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        // ArrayList<Integer> prev = new ArrayList<Integer>();
        // for(int i=0;i<n;i++){
        //     ArrayList<Integer> cur = new ArrayList<Integer>();
        //     cur.addAll(prev);
        //     cur.add(i+1);
        //     cur.addAll(prev);
        //     prev=new ArrayList<Integer>(cur);
        // }
       
        // int start =0;
        // ArrayList<Integer> res = new ArrayList<Integer>();
        // res.add(start);
       
        // for(Integer temp:prev){
        //     start=flipAtPosition(start,temp);
        //     res.add(start);
        // }
        // return res;
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(n == 0){
            res.add(0);
            return res;
        }
        ArrayList<Integer> pre = grayCode(n - 1);
        res.addAll(pre);
       
        for(int j = pre.size() - 1; j >= 0; j--){
            res.add(pre.get(j) + (int)Math.pow(2, n - 1));
        }
        return res;
    }
   
    public int flipAtPosition(int a,int k){
        int temp = (a>>(k-1))&1;
        if(temp==1) return a-(1<<(k-1));
        else return a+(1<<(k-1));
    }
}