526. 优美的排列

🟠   🔖  位运算 数组 动态规划 回溯 状态压缩  🔗 力扣 LeetCode

题目

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

• perm[i] is divisible by i.
• i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

Input: n = 2

Output: 2

Explanation:

The first beautiful arrangement is [1,2]:

• perm[1] = 1 is divisible by i = 1

• perm[2] = 2 is divisible by i = 2

The second beautiful arrangement is [2,1]:

• perm[1] = 2 is divisible by i = 1

• i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1

Output: 1

Constraints:

• 1 <= n <= 15

题目大意

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始 ），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

示例 1：

输入： n = 2

输出： 2

解释：

第 1 个优美的排列是 [1,2]：

• perm[1] = 1 能被 i = 1 整除

• perm[2] = 2 能被 i = 2 整除

第 2 个优美的排列是 [2,1]:

• perm[1] = 2 能被 i = 1 整除

• i = 2 能被 perm[2] = 1 整除

示例 2：

输入： n = 1

输出： 1

提示：

• 1 <= n <= 15

解题思路

1. 回溯函数 backtrack(idx)

   • idx 代表当前填充的位置（从 1 开始）。
   • 当 idx > n 时，说明所有数字已经排列完成，满足条件的方案数 result +1。
   • 否则，遍历 1~n 的所有数字，尝试放入当前 idx 位置：
     • 只有 idx % i == 0 或 i % idx == 0 时，才能继续递归。
     • 使用 used 数组记录已使用的数字，避免重复选择。
     • 回溯后恢复 used 状态（回溯撤销）。

2. 剪枝优化

   • 由于 大的数字更难满足 idx % i == 0，所以我们 倒序遍历 i，让大数优先放入，能更早发现不符合的情况，减少回溯次数。

复杂度分析

• 时间复杂度：O(n^n)
  • 最坏情况下，我们需要遍历 n! 种排列，因此最坏时间复杂度为 O(n!)。
  • 由于剪枝优化（idx % i == 0 || i % idx == 0），搜索空间被大幅减少，实际复杂度远小于 O(n!)，大约在 O(n^n) 级别。
• 空间复杂度：O(n)，使用了一个 used 数组记录已使用的数字。

代码

/**
 * @param {number} n
 * @return {number}
 */
var countArrangement = function (n) {
	let result = 0;
	const used = new Array(n + 1).fill(false); // 长度设为 n+1，方便索引 1~n

	const backtrack = (idx) => {
		if (idx == n + 1) {
			// 递归出口，找到一个合法排列
			result++;
			return;
		}
		for (let i = n; i > 0; i--) {
			// 倒序遍历，减少回溯
			if (!used[i] && (idx % i == 0 || i % idx == 0)) {
				used[i] = true;
				backtrack(idx + 1);
				used[i] = false; // 恢复状态（回溯）
			}
		}
	};

	backtrack(1);
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
667	优美的排列 II		数组 数学	🟠	🀄️ 🔗