每日OJ题_DFS爆搜深搜回溯剪枝②

每日OJ题_DFS爆搜深搜回溯剪枝②_力扣526. 优美的排列

本文主要是介绍每日OJ题_DFS爆搜深搜回溯剪枝②_力扣526. 优美的排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣526. 优美的排列

解析代码

力扣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 整除

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 15

class Solution {
public:int countArrangement(int n) {}
};

解析代码

题意是在每一个位置上考虑所有的可能情况并且不能出现重复。所以可以通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并回溯到上一个状态，直到枚举完所有可能性，得到正确的结果。

需要定义一个变量用来记录所有可能的排列数量，一个一维数组 visited 标记元素，然后从第一个位置开始进行递归。递归函数作用：在当前位置填入一个合理的数字，查找所有满足条件的排列。

class Solution {bool vis[16];int ret;public:int countArrangement(int n) {dfs(1, n);return ret;}void dfs(int pos, int n){if(pos == n + 1) // 下标从1到n{++ret;return;}for(int i = 1; i <= n; ++i){if(!vis[i] && (pos % i == 0 || i % pos == 0)){vis[i] = true;dfs(pos + 1, n);vis[i] = false;}}}
};