循环码排列Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

p[0] = start
p[i] 和 p[i+1] 的二进制表示形式只有一位不同
p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例 1：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：

输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

提示：

1 <= n <= 16
0 <= start < 2^n

# 思路

List<List> res = new ArrayList<>();

# 解法


class Solution {
    
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<Integer> circularPermutation(int n, int start) {
        int[] used = new int[1<<n];
        used[start] = 1;
        path.add(start);
        backtrack(used, n, start);
        return res.get(0);
    }
    public void backtrack(int[] used, int n, int start) {
        if(!res.isEmpty()) return;
        if(path.size() == used.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < n; i++) {
            int option = start ^ (1 << i);
            if(used[option] == 0) {
                used[option] = 1;
                path.add(option);
                backtrack(used, n, option);
                used[option] = 0;
                path.remove(path.size() - 1);
            }
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 总结

分析出几种情况，然后分别对各个情况实现