# My C++ elegant solution with back-tracking

• ``````// 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[n-1]);
ans += counts(n-1, vs);
swap(vs[i], vs[n-1]);
}
}
return ans;
}
};
``````

• @love_FDU_llp I have a question:
why it is not
if (vs[i]%n==0 || n%vs[i]==0) && ((vs[n-1]%(i+1))==0 || (i+1)%vs[n-1])
in the if condition
because you need to make sure the both pair of swap is beautiful arrangement

• @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 [n-1] 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]

• `````` int counts(int n, vector<int> vs) {
``````

can be written as

``````int counts(int n, vector<int> &vs) {
``````

• Hi @onetimetry,

Thanks! Now it's more faster. : )

• @onetimetry Thank you for the answer. so my question here is:
if (vs[i]%n==0 || n%vs[i]==0) {
swap(vs[i], vs[n-1]);

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 post is deleted!

• 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;
}

};
``````

• I'm guessing the reason you don't check if n=0 is valid is because any integer is valid in the first position of the array.

• @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

• @polesun You saved my life!

• @ylc0sky I have the same question with you.
Guess the reason is:

1. Init, every number are in the right position: nums[i] == i;(index start from 1....)
2. 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.
3. And the swap keeps the property of that, so its no need to check the "(vs[n-1]%(i+1))==0 || (i+1)%vs[n-1])".

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 !

• I think if you change for loop condition to
for (int i = n-1; i>=0; i--)
it makes me easier to understand cause it's actually verifying if the number could be divided by index while doing the permutation

• This post is deleted!

• @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; // co-prime
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 space

``````class 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 << (i-1)));
if(k == 0 && (idx%i == 0 || i%idx == 0)){
countArrangementUtil(mask | (1 << (i-1)) , ans , idx + 1 , N);
}
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.