<p>Given 2 integers <code>n</code> and <code>start</code>. Your task is return <strong>any</strong> permutation <code>p</code>&nbsp;of <code>(0,1,2.....,2^n -1) </code>such that :</p>

<ul>
	<li><code>p[0] = start</code></li>
	<li><code>p[i]</code> and <code>p[i+1]</code>&nbsp;differ by only one bit in their binary representation.</li>
	<li><code>p[0]</code> and <code>p[2^n -1]</code>&nbsp;must also differ by only one bit in their binary representation.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, start = 3
<strong>Output:</strong> [3,2,0,1]
<strong>Explanation:</strong> The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, start = 2
<strong>Output:</strong> [2,6,7,5,4,0,1,3]
<strong>Explanation:</strong> The binary representation of the permutation is (010,110,111,101,100,000,001,011).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 16</code></li>
	<li><code>0 &lt;= start&nbsp;&lt;&nbsp;2 ^ n</code></li>
</ul>
// using gray code

class Solution {

public:

    vector<int> circularPermutation(int n, int start) {

        vector<int> grayCode(pow(2, n), 0);

        for (int i = 0; i < (1 << n); i++) {

            // Generating the decimal

            // values of gray code then using

            // bitset to convert them to binary form

            int val = (i ^ (i >> 1));

            grayCode[i] = val;

        }



        auto iter = find(grayCode.begin(), grayCode.end(), start);

        vector<int> ans;

        ans.insert(ans.end(), iter, grayCode.end());

        ans.insert(ans.end(), grayCode.begin(), iter);

        return ans;

    }

};



// arr[0] = start

// arr[2^n -1] = end

// where arr[i] and arr[i+1] differ by 1 bit onyl

// and arr[0] and arr[end] differ by one bit



// inution from the question ane itself (circular permuation) ,which mean

// elements are connected circularly,thats why all consecutive bit diff == 1 and

// most import start and end bit diff ==1 logic : bit additon or bit subtraction

// until 2^n -1 th element is reached (both add and sub will give correct ans) +

// we are sure 2^n -1 bit and start will have bit diff of 1 only eg : n= 2

// ,start = 3 size = 2^2 -1 = 3 (0-indexed) arr (size +1) arr[0] = start 3

// (11)-> oops got wrong (we need flip bits here)



// improve :

// 1.why 2^n -1 ,these represents all possible no that can be generated using n

// bits - 1(As it removed the start num) ,so after fliping n bits u will get

// start back ,thats why called cirular too ,also n in input signfies bit size

// i.e n=3 start =2 then bit rep of start = 010 not 10 prove how fliping n bits

// get to original num : 000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100 ->

// 000 0      1       2      3      4     5       6      7 000 -> 001 -> 011 ->

// 010 -> 110 -> 111 -> 110 -> 010 -> 000 000 -> 100 -> 101 -> 111 -> 110 -> 010

// -> 011 -> 001 -> 000 This proves start and end can be fixes ,there will

// always be n sol available i.e no unique sol remember 2^n -1 is all unique

// bits that can be flip ,thats mean no numer will be repeated again in this

// ,i.e u can do this 000 -> 010 -> 110 -> 100  ,as we need to flip each bit 2

// times logic : there is no such pattern here to remove bits ,if followed last

// bits and first bit diff !=1 so try all possiblity i.e 2^n (TC) validating TC:

// 2^16 = 2^10 * 2^6 => 10^3 * 2^6 <=10^8 logic : include not include untill u

// get start back + calls 2^n -1 NOTE: u may think of flipping each bit once

// from a single call i.e 00001 -> flip(1),flip(2),flip(3) ,flip(4).. all non

// ones -> but this may end up wrong + complexcity wise also u may think it will

// not go 2^n but more +  will go complex require backtracking + recursion

class Solution2 {

    bool solve(int curr, int end, vector<int>& ans, int currBit = 0) {

        if (curr == end) {

            ans.push_back(curr);

            return true;

        } else {

            return false;

        }



        int num = ~(1 << currBit);

        ans.push_back(curr & num);

        bool res1 = solve(curr & num, end, ans, currBit + 1);



        if (!res1) {

            ans.pop_back();

            bool res1 = solve(curr & num, end, ans, currBit + 1);

        }

    }



public:

    vector<int> circularPermutation(int n, int start) {

        return {

            // couldn;t how to generate and try all combination

        };

    }

};
20000