// By lovellp
// Time: 6ms
class Solution {
public:
int countArrangement(int N) {
vector<int> vs;
for (int i=0; i<N; ++i) vs.push_back(i+1);
return counts(N, vs);
}
int counts(int n, vector<int>& vs) {
if (n <= 0) return 1;
int ans = 0;
for (int i=0; i<n; ++i) {
if (vs[i]%n==0  n%vs[i]==0) {
swap(vs[i], vs[n1]);
ans += counts(n1, vs);
swap(vs[i], vs[n1]);
}
}
return ans;
}
};
My C++ elegant solution with backtracking


@ylc0sky Each step during recursion takes care of one position at a time, i.e, n  1. the position [i] (let's say i = 3) will be processed when recursion reaches that. That's why there's no need to worry about whether this position meets arrangement criteria in the current [n1] step. When the vs[3] (where the input parameter n = 4) is handled in subsequent recursion, the value will be decided from the remainder elements vs[0], vs[1], vs[2], vs[3]

said in My C++ elegant solution with backtracking:
int counts(int n, vector<int> vs) {
can be written as
int counts(int n, vector<int> &vs) {


@onetimetry Thank you for the answer. so my question here is:
if (vs[i]%n==0  n%vs[i]==0) {
swap(vs[i], vs[n1]);In this above code, after swap, I think it still need to make sure that i and vs[n] should also be beautiful arrangement

This is my code. what's wrong cannot figure it out
class Solution { public: int ret = 0; int countArrangement(int N) { vector<int> v(N,0); for(int i=0;i<v.size();i++) { v[i] = i+1; } solve(0, v, N); return ret; } void solve(int pos, vector<int>& v, int length) { if(pos >=length) { for_each(v.begin(), v.end(), [](int n){cout<<n<<" ";}); cout<<endl; ret++; return; } for(int i=0;i<=pos;i++) { if(isBeauty(v[i], pos+1)&&isBeauty(v[pos],i+1)) { swap(v[i], v[pos]); solve(pos+1, v, length); swap(v[i], v[pos]); } } } bool isBeauty(int pos, int val) { return pos%val==0  val%pos == 0; } };

@ylc0sky
when n = 6, you cannot get [2 6 1 4 5 3] it should come from [2 3 1 4 5 6], but [2 3 1 4 5] is invalid when n = 5


@ylc0sky I have the same question with you.
Guess the reason is: Init, every number are in the right position: nums[i] == i;(index start from 1....)
 Then, if nums[i]%n==0  n%nums[i]==0 is true, then i % n  nums[n] % i is also true, both situation indicates safe to swap.
 And the swap keeps the property of that, so its no need to check the "(vs[n1]%(i+1))==0  (i+1)%vs[n1])".
Just guess, hope someone can give a entire proof.

@NeoMatrix I think you are right, but if you can give an entire proof, that will be more convincing !

@ylc0sky, it is not necessary to guarantee vs[n] is beautiful at position i at the time when n>i+1 because in the later loop when n=i+1 the if statement will check it. My understanding of invariant for the loop is all numbers in position [n, vs.size) are beautiful and numbers in [0,n) are not. When n==0, everything is beautiful and we count it as one.

C++ backtracking using bool array to indicate if a number is used or not
class Solution { public: int countArrangement(int N) { if(N<1) return 0; vector<bool> used(N+1,false); return dfs(N,1,used); } private: int dfs(int N, int i, vector<bool>& used) { if(i>N) return 1; // term. cond. int sum = 0; for(int num=1; num<=N; num++) { if(used[num]) continue; if(num%i!=0 && i%num!=0) continue; // coprime used[num]=true; sum+=dfs(N,i+1,used); used[num]=false; } return sum; } };

Hi
Since the size of N <= 15 you can also use bitmasks and save spaceclass Solution { public: int countArrangement(int N) { if(N <= 1)return N; int ans = 0 , mask = 0; countArrangementUtil(mask , ans , 1 ,N); return ans; } void countArrangementUtil(const int mask , int& ans , const int idx ,const int N){ if(idx == N + 1){ ans++ ; return; } for(int i = 1; i <= N ; ++i){ int k = (mask & (1 << (i1))); if(k == 0 && (idx%i == 0  i%idx == 0)){ countArrangementUtil(mask  (1 << (i1)) , ans , idx + 1 , N); } } } };