优美的排列 图解题解

这道题到底在问什么

输入

n = 2

输出

2 （[1,2] 和 [2,1] 都满足）

输入

n = 3

输出

3 （[1,2,3]、[2,1,3]、[3,2,1]）

最优解：一步一步想明白

1. 3记住这套「能放就放、放满计一种、放不下就回退换数」，下面每一帧都在套它。
2. 4上面一排是能用的数字 1、2、3、4，下面 path 是正在拼的排列。规矩很简单：把数字 x 放进位置 i，要么 x 能整除 i，要么 i 能整除 x，满足一个就行。
3. 5位置 1 先放数字 1。任何数除以 1 都余 0，1 当然能整除位置 1，放下去。path 现在是 [1]。
4. 6来到位置 2。先看数字 1，可它已经放过了，变灰不能再用，跳过它。
5. 7再看数字 3：3 除以 2 余 1，2 除以 3 也除不尽，3 和位置 2 互相都整除不了，放不进来。
6. 8数字 2 还没用，而且 2 除以 2 余 0，正好整除位置 2，放进来。path 变成 [1, 2]。
7. 9位置 3：数字 1 已用跳过；数字 3 除以 3 余 0，能整除位置 3，放下去。path 变成 [1, 2, 3]。
8. 10位置 4：1、2、3 都用过了，只剩数字 4，4 除以 4 余 0，放进来。path 变成 [1, 2, 3, 4]。
9. 11四个位置全放满了，这就是一种优美的排列 [1, 2, 3, 4]，收进右边结果区。已经找到 1 种。
10. 12这条路走到底了，开始回退：位置 4、位置 3、位置 2 放的数字依次撤掉，path 缩回到只剩 [1]，回到位置 2 去换个别的数字。
11. 13位置 2 这次改放数字 4：4 除以 2 余 0，数字 4 能被位置 2 整除，放下去。path 变成 [1, 4]。
12. 14位置 3：1、4 都用过，候选里剩数字 3，3 除以 3 余 0，放进来。path 变成 [1, 4, 3]。
13. 15位置 4 只剩数字 2。这次反过来看：位置 4 除以数字 2 余 0，数字 2 能整除位置 4 也算数，放进来。path 变成 [1, 4, 3, 2]。
14. 16又放满了，这是第 2 种优美排列 [1, 4, 3, 2]，收进结果。已经找到 2 种。
15. 17位置 1 放 1 的所有分支都试完了，回到最开头，位置 1 改放数字 2，重新往后搜。
16. 18沿同一套规则往下放：位置 2 放 1（位置 2 除以 1 余 0），位置 3 放 3，位置 4 放 4，凑出第 3 种 [2, 1, 3, 4]。
17. 19回到位置 2 换成数字 4，再往下放，得到第 4 种 [2, 4, 3, 1]。已经找到 4 种。
18. 20位置 1 再换成数字 3，继续往后搜。
19. 21逐位套整除规则放下去，得到第 5 种 [3, 2, 1, 4]。
20. 22换条岔路再放，得到第 6 种 [3, 4, 1, 2]。已经找到 6 种。
21. 23位置 1 最后换成数字 4，把最后一类起手也搜一遍。
22. 24放出第 7 种 [4, 1, 3, 2]。
23. 25最后放出第 8 种 [4, 2, 3, 1]。
24. 26位置 1 的四种起手（1、2、3、4）全都搜过，回溯把每一种可能都走遍，右边正好攒了 8 种优美的排列。所以 n = 4 的答案就是 8。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
            }
        }
    }
};

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;
            }
        }
    }
}

复杂度

面试官可能追问