Leetcode526Beautifulnumber

题意

n个数组成排列，排列的下标为i从1开始，并且排列中的每一个数都满足性质,nums[i]能被i整除，或者i被nums[i]整除，求一共有多少个这样的数列

题解

用一个长度为n+1的数组（因为下标从1开始），来记录1-n是否已经选过。用dfs对数列中的每一个位置i搜索如果nums[i]能被i整除，或者i被nums[i]整除。如果最后形成的数列长度为n那么这样的数列就是满足条件的

代码 class Solution { public: int cnt; vector<bool> a; int countArrangement(int n) { a.resize(n+1, false); dfs(n, 0); return cnt; } void dfs(int n, int u) { if(u == n) { cnt++; return; } for(int i = n; i >= 1; i--) { if(!a[i] && (i % (u+1) == 0 || (u+1) % i == 0)) { a[i] = true; dfs(n, u+1); a[i] = false; } } } };

时间复杂度 O ( n ! ) O(n!) O(n!) 空间复杂度 O ( n ) O(n) O(n)