1238. Circular Permutation in Binary Representation

Here is the discussion post.

C# Design algorithm using DFS similar to Sudoku solver

It is a medium level algorithm which can be solved using depth first search. The challenge part is to work on bit manipulation, how to change one bit from index = 0 to index = 15?

Case study:
I need to warmup bit manipulation to learn to solve two problems in the following:

1. Change one bit - how to change it?
   Use bit operator XOR. As we know, 0 ^ 0 = 0, 0 ^1 = 1, 1 ^ 1 = 0; and there are 16 bits to alter, and we can use left shift operator to generate an integer to set nth bit to 1 whereas n is from 0 to 15. In other words, I have to come out the express 1 << i.
   So, the answer is last ^ (1 << i), whereas is from 0 to 15.
2. How to prove two numbers are the same except one bit?
   Assume that m and n only have one bit different, so m ^ n = 2^p, p is from p to 15. And p & (p - 1) = 0 <=> all bits from 0 to p should be 0.

Here are highlights:

1. Understand how to run DFS to search all possible paths until one path is found.
2. Work on DFS search - base case, backtracking, mark visited using HashSet to avoid deadloop;
3. Time complexity and space analysis is similar to my favorite algorithm Sudoku solver.

Actionable Items
I could not solve the algorithm in weekly contest 160 on Oct. 26, 2019. I spent over 20 minutes to analyze, but I could not come out using DFS algorithm to work on all bits from 0 to 15.
I have to practice more often in weekdays, solve more medium algorithms.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1238_circular_permutation
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// 1238 Circular Permutation in Binary Representation
        /// The idea is similar to Sudoku solver; Each step using DFS to search all options. 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="start"></param>
        /// <returns></returns>
        public IList<int> CircularPermutation(int n, int start)
        {
            var result = new List<int>();

            var set = new HashSet<int>();
            result.Add(start);
            set.Add(start);

            runDFS(n, set, result, start);
            return result; 
        }

        /// <summary>
        /// similar to Sudoku solver
        /// backtracking 
        /// DFS path - mark visited
        /// </summary>
        /// <param name="n"></param>
        /// <param name="hashSet"></param>
        /// <param name="result"></param>
        /// <param name="start"></param>
        /// <returns></returns>
        private static bool runDFS(int n, HashSet<int> hashSet, IList<int> result, int start)
        {
            if (hashSet.Count == (int)Math.Pow(2, n))
            {
                int x = result[result.Count - 1] ^ start; // XOR operator - first and last are different
                return (x & (x - 1)) == 0; 
            }

            var length = result.Count;
            int last = result[length - 1];

            for (int i = 0; i < 16; i++)
            {
                int next = last ^ (1 << i); // XOR operator - change ith bit 
                if (next <= (Math.Pow(2, n) - 1) && !hashSet.Contains(next))
                {
                    hashSet.Add(next);
                    result.Add(next); 

                    if(runDFS(n, hashSet, result, start))
                    {
                        return true; 
                    }

                    hashSet.Remove(next);
                    result.RemoveAt(result.Count - 1);
                }
            }

            return false; 
        }
    }
}