Circular Permutation in Binary Representation

This approach uses a classic backtracking algorithm to explore all possible permutations. It builds the sequence one number at a time, ensuring each new number satisfies the single-bit-difference rule. If it reaches a dead end, it backtracks to try another path. This is conceptually a search for a Hamiltonian Path in an n-dimensional hypercube graph.

• Initialize a result list with start.
• Initialize a visited set with start.
• Define a recursive function solve():
  • If result.size() == 2^n:
    • Check if result.get(0) and result.get(result.size() - 1) differ by one bit.
    • If they do, return true. Otherwise, return false.
  • Get last = result.get(result.size() - 1).
  • For i from 0 to n-1:
    • Calculate next = last ^ (1 << i).
    • If next is not in visited:
      • Add next to result and visited.
      • If solve() returns true, return true.
      • Backtrack: remove next from result and visited.
  • Return false.
• Call solve() to populate the result list.

The algorithm starts with a list containing only the start element. A visited set is used to keep track of numbers that are already part of the sequence to avoid cycles and redundant computations. A recursive function is defined to build the permutation. In each recursive call, it takes the last element added to the sequence and tries to find a valid next element by flipping each of its n bits one by one. A candidate is valid if it hasn't been visited yet. If a valid candidate is found, it's added to the sequence, and the function calls itself. If the recursive call fails to find a complete path, the candidate is removed (this is the backtracking step). The base case for the recursion is when the sequence length reaches 2^n. At this point, a final check is performed to ensure the circular condition (the first and last elements differ by one bit) is met. If so, a solution has been found.

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        result.add(start);
        visited.add(start);
        backtrack(n, (1 << n), result, visited);
        return result;
    }

    private boolean backtrack(int n, int totalSize, List<Integer> result, Set<Integer> visited) {
        if (result.size() == totalSize) {
            int first = result.get(0);
            int last = result.get(result.size() - 1);
            int xor = first ^ last;
            // Check if xor is a power of 2
            return (xor > 0) && ((xor & (xor - 1)) == 0);
        }

        int last = result.get(result.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = last ^ (1 << i);
            if (!visited.contains(next)) {
                visited.add(next);
                result.add(next);
                if (backtrack(n, totalSize, result, visited)) {
                    return true;
                }
                // Backtrack
                visited.remove(next);
                result.remove(result.size() - 1);
            }
        }
        return false;
    }
}