假设我们有从1到N的N个整数。如果此数组中的第i个位置(1 <= i <= N)满足以下条件之一,则将定义一个漂亮的排列为完全由这N个数字构成的数组-
第i个位置的数字可以除以i。
我可以被第i个位置的数字整除。
因此,如果输入为2,则结果也将为2,因为第一个漂亮的排列是[1,2]。此处,第1位置(i = 1)的数字为1,i被i(i = 1)整除。然后,第二个位置(i = 2)的数字为2,而2可被i整除(i = 2)。第二个漂亮的排列是[2,1]:这里第一个位置(i = 1)的数字是2,而2可以被i(i = 1)整除。然后,第二个位置(i = 2)的数字为1,而i(i = 2)可被1整除。
为了解决这个问题,我们将遵循以下步骤-
定义一个递归方法solve()
,它将采用访问数组,结束符和位置。pos最初是1。
如果pos = end + 1,则将ans加1并返回
对于我在范围1到结束
将我标记为已访问
解决(已访问,结束,位置+1)
将我标记为未访问
如果未访问我并且pos可被0整除或i被0整除,则
从主要方法中,执行以下操作-
ans:= 0,创建一个名为访问的数组
调用solve(visited,N,1)r
返回ans。
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int ans; void solve(vector <bool>& visited, int end, int pos = 1){ if(pos == end + 1){ ans++; return; } for(int i = 1; i <= end; i++){ if(!visited[i] && (pos % i == 0 || i % pos == 0)){ visited[i] = true; solve(visited, end, pos + 1); visited[i] = false; } } } int countArrangement(int N) { ans = 0; vector <bool> visited(N); solve(visited, N); return ans; } }; main(){ Solution ob; cout << (ob.countArrangement(2)); }
2
输出结果
2