优美的排列 图解题解

优美排列到底在数满足整除的排法有几种

有 1 到 n 这 n 个整数，排成数组 perm，位置从 1 数起。只要每个位置都满足「perm[i] 能被 i 整除」或「i 能被 perm[i] 整除」其一，就叫优美排列。问一共能排出多少个优美排列。题面给 n=2 答案 2（[1,2] 和 [2,1] 都行），n=3 答案 3（[1,2,3]、[2,1,3]、[3,2,1]）。要的是总个数，不是某个排列。

为什么把 n 个数的全排列都摆出来会算不动

最直接是把全排列（1 到 n 的所有排法）都列出来，逐位检查整除条件，满足就计数。可 n 个数的全排列有 n! 个，n=15 就是一万三千亿个，光生成完就跑不动。而且大量排列在很靠前就已违规：首位放个和位置 1 对不上的数，后面怎么填都白填，笨办法却还要把这条死路铺满。违规能提前发现，就边填边判，某位放不下立刻掉头，不必等整条拼完。

一个位置能放哪些数，为什么两个整除方向都得判

位置 i 能放数字 x 的条件是 i 整除 x 或者 x 整除 i，满足一个就行。两个方向缺一不可——只判 x 整除 i（位置 2 只收 2、4、6…）会漏掉「i 整除 x」那半边，位置 1 能收所有数正是靠这一侧。参考代码先花 O(n²) 把关系表 match 建好：对每个位置 i 扫一遍 1 到 n，把满足 j%i==0 或 i%j==0 的数字 j 收进 match[i]。往后每到一位直接从候选表挑。

逐位放数、放完撤标记，回溯怎么做到不重不漏

从位置 1 起逐位往后放，这就是回溯（沿一条路径往下试，走不通就退回上一步换个选择）。到位置 i 时，遍历 match[i] 里还没用过的数字 j，用 vis 数组标记 j 已占用，再递归（函数自己调用自己，去处理下一位）填位置 i+1；等这条分支所有可能都试完、递归返回，立刻把 vis[j] 撤回没用过。这一撤是关键：不撤销，这个数字会被当成永久占用，别的分支就再用不上，会漏掉一大批合法排列。当位置填到 n+1，说明每位都合法放满，答案加一。

拿 n=3 亲手把三种优美排列搜出来

先建 match 表：位置 1 收 1、2、3；位置 2 收 1、2；位置 3 收 1、3。

位置 1 放 1：位置 2 只剩 2，位置 3 只剩 3，拼成 [1,2,3]，第 1 种。位置 1 放 2：位置 2 放 1、位置 3 放 3，得 [2,1,3]，第 2 种。位置 1 放 3：位置 2 若放 1，位置 3 的候选 1、3 全被占，走死回退；位置 2 改放 2、位置 3 放 1，得 [3,2,1]，第 3 种。三条起手搜完，答案 3，和题面对上。

回溯为什么不超时，撤销和从 1 起编号两个坑

搜索树（所有尝试分支长成的一棵树）最坏有 O(n!) 个节点，但整除条件剪掉大量分支，实际远小于上界，n=15 也就几万到几十万次，能过。空间主要是预存的 match 表 O(n²)，加 vis 数组和递归栈 O(n)。两个坑最容易踩：一是递归返回后忘撤销 vis 标记，数字被当永久占用，会少算很多排列；二是位置和数字都从 1 编号，从 0 起会让「i 整除 x」变成除以 0 出错。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countArrangement(self, n: int) -> int:
        def dfs(i):
            nonlocal ans, n
            if i == n + 1:
                ans += 1
                return
            for j in match[i]:
                if not vis[j]:
                    vis[j] = True
                    dfs(i + 1)
                    vis[j] = False

        ans = 0
        vis = [False] * (n + 1)
        match = defaultdict(list)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if j % i == 0 or i % j == 0:
                    match[i].append(j)

        dfs(1)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int n;
    int ans;
    vector<bool> vis;
    unordered_map<int, vector<int>> match;

    int countArrangement(int n) {
        this->n = n;
        this->ans = 0;
        vis.resize(n + 1);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i % j == 0 || j % i == 0)
                    match[i].push_back(j);
        dfs(1);
        return ans;
    }

    void dfs(int i) {
        if (i == n + 1) {
            ++ans;
            return;
        }
        for (int j : match[i]) {
            if (!vis[j]) {
                vis[j] = true;
                dfs(i + 1);
                vis[j] = false;
            }
        }
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int n;
    private int ans;
    private boolean[] vis;
    private Map<Integer, List<Integer>> match;

    public int countArrangement(int n) {
        this.n = n;
        ans = 0;
        vis = new boolean[n + 1];
        match = new HashMap<>();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i % j == 0 || j % i == 0) {
                    match.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
                }
            }
        }
        dfs(1);
        return ans;
    }

    private void dfs(int i) {
        if (i == n + 1) {
            ++ans;
            return;
        }
        if (!match.containsKey(i)) {
            return;
        }
        for (int j : match.get(i)) {
            if (!vis[j]) {
                vis[j] = true;
                dfs(i + 1);
                vis[j] = false;
            }
        }
    }
}