526. 优美的排列
题目描述
输入正整数 n，把 1 到 n 这 n 个数排成一个排列 perm，位置编号从 1 开始。
如果对每个位置 i，都满足 perm[i] 能被 i 整除，或者 i 能被 perm[i] 整除（两者至少成立一个），就称这个排列是优美的。
返回优美排列的个数。
示例 1
输入：n = 2 输出：2
解释：[1,2] 和 [2,1] 在每个位置都满足整除关系。
示例 2
输入：n = 1 输出：1
解释：只有排列 [1]。
数据范围
1 <= n <= 15
解题思路
按位置 1、2、…、n 依次填数。对位置 i，枚举所有还没用过的 x，只有满足 x % i == 0 或 i % x == 0 才放进去，然后递归填下一个位置，回来后撤销。不满足条件的分支立刻剪掉，所以搜索量远小于 n!。填满 n 个位置就找到一个优美排列，计数加 1。
为什么正确
进入 dfs(i) 时，位置 1..i-1 已填好，每个位置都满足整除条件，used 恰好标记这些已用的数。
复杂度分析
时间最坏 O(n!)（实际剪枝后很小），空间 O(n)。
易错点
整除条件是“或”关系，两个方向都要检查；另外递归返回后必须把 used[x] 改回 False，否则后续分支会少数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countArrangement(self, n: int) -> int:
used = [False] * (n + 1)
def dfs(i):
if i > n:
return 1
total = 0
for x in range(1, n + 1):
if not used[x] and (x % i == 0 or i % x == 0):
used[x] = True
total += dfs(i + 1)
used[x] = False
return total
return dfs(1)class Solution {
boolean[] used;
int n;
public int countArrangement(int n) {
this.n = n;
used = new boolean[n + 1];
return dfs(1);
}
int dfs(int i) {
if (i > n) {
return 1;
}
int total = 0;
for (int x = 1; x <= n; x++) {
if (!used[x] && (x % i == 0 || i % x == 0)) {
used[x] = true;
total += dfs(i + 1);
used[x] = false;
}
}
return total;
}
}class Solution {
public:
int countArrangement(int n) {
vector<bool> used(n + 1, false);
function<int(int)> dfs = [&](int i) -> int {
if (i > n) {
return 1;
}
int total = 0;
for (int x = 1; x <= n; x++) {
if (!used[x] && (x % i == 0 || i % x == 0)) {
used[x] = true;
total += dfs(i + 1);
used[x] = false;
}
}
return total;
};
return dfs(1);
}
};func countArrangement(n int) int {
used := make([]bool, n+1)
var dfs func(i int) int
dfs = func(i int) int {
if i > n {
return 1
}
total := 0
for x := 1; x <= n; x++ {
if !used[x] && (x%i == 0 || i%x == 0) {
used[x] = true
total += dfs(i + 1)
used[x] = false
}
}
return total
}
return dfs(1)
}var countArrangement = function(n) {
const used = new Array(n + 1).fill(false);
const dfs = (i) => {
if (i > n) {
return 1;
}
let total = 0;
for (let x = 1; x <= n; x++) {
if (!used[x] && (x % i === 0 || i % x === 0)) {
used[x] = true;
total += dfs(i + 1);
used[x] = false;
}
}
return total;
};
return dfs(1);
};function countArrangement(n: number): number {
const used: boolean[] = new Array(n + 1).fill(false);
const dfs = (i: number): number => {
if (i > n) {
return 1;
}
let total = 0;
for (let x = 1; x <= n; x++) {
if (!used[x] && (x % i === 0 || i % x === 0)) {
used[x] = true;
total += dfs(i + 1);
used[x] = false;
}
}
return total;
};
return dfs(1);
}其他解法
回溯直接枚举排列，靠整除条件剪枝；状态压缩 DP 发现后续方案数只取决于已用数字集合，把它作为状态进行合并计数。
解法 2：状态压缩动态规划 时间 O(n·2ⁿ)，空间 O(2ⁿ)
按位置从 1 到 n 依次放数字。用二进制数 mask 表示已经用掉的数字集合，它的 1 的个数 i 就是已放好的位置数。f[mask] 表示这种情况下的方案数；转移时枚举最后放在位置 i 的数字 x，若 x 在 mask 中且 x 与 i 满足整除关系，就把 f[mask 去掉 x] 加到 f[mask]。答案是 f[全集]。
把回溯中重复出现的“剩余数字集合相同”的子问题合并，复杂度不依赖剪枝效果。要占用 2ⁿ 的数组，只适合 n 较小的情况。
class Solution:
def countArrangement(self, n: int) -> int:
# f[mask]：已用数字集合为 mask 时，前 popcount(mask) 个位置的合法排列数
f = [0] * (1 << n)
f[0] = 1
for mask in range(1, 1 << n):
i = bin(mask).count('1') # 最后放的是第 i 个位置
for x in range(1, n + 1):
# 数字 x 放在位置 i
if mask >> (x - 1) & 1 and (x % i == 0 or i % x == 0):
f[mask] += f[mask ^ (1 << (x - 1))]
return f[(1 << n) - 1]class Solution {
public int countArrangement(int n) {
int[] f = new int[1 << n];
f[0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
int i = Integer.bitCount(mask);
for (int x = 1; x <= n; x++) {
if ((mask >> (x - 1) & 1) == 1 && (x % i == 0 || i % x == 0)) f[mask] += f[mask ^ (1 << (x - 1))];
}
}
return f[(1 << n) - 1];
}
}class Solution {
public:
int countArrangement(int n) {
vector<int> f(1 << n, 0);
f[0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
int i = __builtin_popcount(mask);
for (int x = 1; x <= n; x++) {
if ((mask >> (x - 1) & 1) && (x % i == 0 || i % x == 0)) f[mask] += f[mask ^ (1 << (x - 1))];
}
}
return f[(1 << n) - 1];
}
};func countArrangement(n int) int {
f := make([]int, 1<<n)
f[0] = 1
for mask := 1; mask < 1<<n; mask++ {
i := 0
for m := mask; m > 0; m &= m - 1 {
i++
}
for x := 1; x <= n; x++ {
if mask>>(x-1)&1 == 1 && (x%i == 0 || i%x == 0) {
f[mask] += f[mask^(1<<(x-1))]
}
}
}
return f[1<<n-1]
}var countArrangement = function(n) {
const f = new Array(1 << n).fill(0);
f[0] = 1;
for (let mask = 1; mask < (1 << n); mask++) {
let i = 0;
for (let m = mask; m > 0; m &= m - 1) i++;
for (let x = 1; x <= n; x++) {
if ((mask >> (x - 1) & 1) && (x % i === 0 || i % x === 0)) f[mask] += f[mask ^ (1 << (x - 1))];
}
}
return f[(1 << n) - 1];
};function countArrangement(n: number): number {
const f = new Array(1 << n).fill(0);
f[0] = 1;
for (let mask = 1; mask < (1 << n); mask++) {
let i = 0;
for (let m = mask; m > 0; m &= m - 1) i++;
for (let x = 1; x <= n; x++) {
if ((mask >> (x - 1) & 1) && (x % i === 0 || i % x === 0)) f[mask] += f[mask ^ (1 << (x - 1))];
}
}
return f[(1 << n) - 1];
}