力扣526——优美的排列（回溯）

本文主要是介绍力扣526——优美的排列（回溯），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目（中等）
假设有从 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 整除

提示：
1 <= n <= 15

思路
回溯，设一个访问数组，标记某个数字是否已用

代码

class Solution {
private:
    vector<int> vis = vector<int>(20, 0);
    int ans = 0;
public:    
    void dfs(int pos, int n) {
        if(pos > n) ans++;
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            if(pos % i == 0 || i % pos == 0) {
                vis[i] = 1;
                dfs(pos + 1, n);
                vis[i] = 0;
            }
        }
        return;
    }
    int countArrangement(int n) {
        dfs(1, n);
        return ans;
    }
};

这篇关于力扣526——优美的排列（回溯）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！