526. Beautiful Arrangement -----------M

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 1:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 15

A:

Idea is straightforward,  just swap and check position.

class Solution {
public:
    int countArrangement(int n) {
        vector<int> V;
        for(int i =1; i<=n ; i++)
            V.push_back(i);
        int res=0;
        helper(V, 0, res);
        return res;
    }
private:
    void helper(vector<int>& V, int idx, int & res){
        int n = V.size();
        if(idx>= n){
            res++;
            return;
        }
        for(int j= idx; j < n; j++){
            swap(V[idx], V[j]);
            if(V[idx] %(idx+1) ==0 || (idx+1) % V[idx] == 0){
                helper(V, idx+1, res);
            }
            swap(V[idx], V[j]);
        }
    }
};

犯了一个极其SB的错误，  忘记了是1 indexed

就是为了图快，哎。