难度: Medium
假设有从 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运行时间: 32 ms
内存: 16.0 MB
class Solution:
def countArrangement(self, n: int) -> int:
self.res = 0
match = defaultdict(list)
for i in range(1, n+1):
for j in range(1, n+1):
if i%j == 0 or j%i == 0:
match[i].append(j)
vis = set()
def backtrack(index):
if index == n+1:
self.res += 1
for x in match[index]:
if x not in vis:
vis.add(x)
backtrack(index+1)
vis.discard(x)
backtrack(1)
return self.res
这个题解采用了回溯法来解决问题。首先，为了方便查找每个位置 i 可以放置哪些数字，创建了一个字典 match，其中 match[i] 包含所有可以放在位置 i 的数字（即满足 perm[i] 能被 i 整除或 i 能被 perm[i] 整除的数）。接着，使用 vis 集合来跟踪哪些数字已经在排列中被使用过。backtrack 函数从位置 1 到 n 递归地尝试所有可能的数字，如果构成了一个优美的排列，则增加结果计数器 self.res。
时间复杂度: O(n!)
空间复杂度: O(n^2)
class Solution:
def countArrangement(self, n: int) -> int:
self.res = 0 # 结果计数器
match = defaultdict(list) # 存储每个位置可以放哪些数字
for i in range(1, n+1):
for j in range(1, n+1):
if i%j == 0 or j%i == 0: # 检查是否满足优美排列的条件
match[i].append(j)
vis = set() # 跟踪已使用的数字
def backtrack(index):
if index == n+1: # 若达到排列的尾部
self.res += 1 # 找到一个有效的排列
for x in match[index]: # 尝试每个可以放在当前位置的数字
if x not in vis: # 如果数字还没被使用
vis.add(x) # 标记为已使用
backtrack(index+1) # 递归到下一个位置
vis.discard(x) # 回溯，撤销此次选择
backtrack(1) # 从位置 1 开始回溯
return self.res
在构建`match`字典时预先存储每个位置可以放置哪些数字，是为了优化算法的效率。这种预处理方式可以避免在回溯过程中的重复计算，每到一个新的位置时，不需要再次计算哪些数字可以放在当前位置，只需要查询已经存储的信息即可。这样减少了计算量，加快了算法的执行速度。同时，这也使得我们的代码更加整洁、易于理解和维护。
在递归函数`backtrack`中，我们使用了`vis`集合来跟踪哪些数字已经被使用。在每次递归调用前，如果一个数字`x`可以放在当前位置`index`并且尚未被使用，则将其加入到`vis`集合中表示这个数字已经被占用。在递归返回后，需要撤销这一选择，即从`vis`集合中移除数字`x`。这样，每次递归调用都保持了`vis`集合的正确性，确保了每个数字在排列中只被使用一次，从而避免了重复使用同一个数字。
在`backtrack`函数的设计中，每一步递归都严格保证了选择的数字`x`满足优美排列的条件（`perm[i]`能被`i`整除或`i`能被`perm[i]`整除），这是通过`match[index]`确保的。因此，当`index`达到`n+1`时，意味着已经成功地放置了从1到n的所有数字，并且每个数字的放置都是有效的。所以，此时的排列已经是一个有效的优美排列，不需要进一步的验证，可以直接将结果计数器`res`增加1。