?LeetCode刷題實戰(zhàn)526： 優(yōu)美的排列
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i] is divisible by i.
i is divisible by perm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
perm[i] 能夠被 i 整除
i 能夠被 perm[i] 整除
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例 1：
輸入：n = 2
輸出：2
解釋：
第 1 個優(yōu)美的排列是 [1,2]：
????- perm[1] = 1 能被 i = 1 整除
????- perm[2] = 2 能被 i = 2 整除
第 2 個優(yōu)美的排列是 [2,1]:
????- perm[1] = 2 能被 i = 1 整除
????- i = 2 能被 perm[2] = 1 整除
示例 2：
輸入：n = 1
輸出：1
解題
class?Solution?{
public:
????int?res = 0;
????int?n;
????vector<bool> visited; // 判斷某個數(shù)字是否已經(jīng)在當前排列出現(xiàn)過
????void?dfs(int?u, vector<bool>& visited)?{
????????if(u == n + 1) { // 找到一個滿足條件的排列，答案++
????????????++res;
????????????return?;
????????}
????????for(int?i = 1; i <= n; ++i) {
????????????if(visited[i] == false?&& ((u % i == 0) || (i % u == 0))) { // 當前數(shù)字沒有排列中出現(xiàn)過，且滿足題目要求的條件，則嘗試在當前位置放上數(shù)字i，再繼續(xù)搜索下一個位置
????????????????visited[i] = true;
????????????????dfs(u + 1, visited);
????????????????visited[i] = false;
????????????}
????????}
????}
????int?countArrangement(int?N)?{
????????n = N;
????????visited = vector<bool>(n + 1, false);
????????dfs(1, visited);
????????return?res;
????}
};