Sắp xếp đẹp (Beautiful Arrangement) trong C++

Cho N số 1..N. Hoán vị gọi là "đẹp" nếu tại vị trí i (1-based), số đó chia hết cho i hoặc i chia hết cho số đó. Đếm số hoán vị đẹp.

Ví dụ: N=2 → 2 hoán vị: [1,2] và [2,1].

Thuật toán (Backtracking + Pruning)

1. Duyệt vị trí pos từ 1 đến N.
2. Thử từng số chưa dùng thỏa mãn điều kiện chia hết.
3. Đánh dấu đã dùng, đệ quy pos+1, bỏ đánh dấu (backtrack).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int ans = 0;
    void solve(vector& used, int N, int pos=1) {
        if (pos == N+1) { ans++; return; }
        for (int i=1; i<=N; i++) {
            if (!used[i] && (pos%i==0 || i%pos==0)) {
                used[i]=true;
                solve(used, N, pos+1);
                used[i]=false;
            }
        }
    }
public:
    int countArrangement(int N) {
        ans=0;
        vector used(N+1,false);
        solve(used, N);
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.countArrangement(2); // 2
    return 0;
}

Đầu vào / Đầu ra

Input: 2

Output: 2