Beautiful Arrangement

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.

Example:

Input:  n=2
Output: 2

Approach

Java

public class BeautifulArrangement {
    static int[] vis;
    public static void main(String[] args) {
        int n = 2;
        System.out.println(countArrangement(n));
    }
    static int countArrangement(int n) {
        vis = new int[n + 1];
        int ans = dfs(1, n);
        return ans;
    }
    static int dfs(int start, int end) {
        // base case
        if (start > end)
            return 1;
        int ans = 0;
        // iterate for all values
        for (int i = 1; i <= end; i++) {
            if (vis[i] == 0 && (i % start == 0 || start % i == 0)) {
                vis[i] = 1;
                ans += dfs(start + 1, end);
                vis[i] = 0;
            }
        }
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> vis;
int dfs(int start,int end)
{
    //base case
    if(start>end)
        return 1;
    int ans=0;
    //iterate for all values
    for(int i=1;i<=end;i++)
        {
            if(vis[i]==0&&(i%start==0||start%i==0))
            {
                vis[i]=1;
                ans+=dfs(start+1,end);
                vis[i]=0;
            }
        }
        return ans;
}
int countArrangement(int n) 
{
        
        vis.resize(n+1);
        vis.clear();
        int ans=dfs(1,n);
        return ans;
}
int main()
{
    int n=2;
    cout<<countArrangement(n);
    return 0;
}