Beautiful Arrangement นับการจัดเรียงที่สวยงามใน C++

ให้จำนวนเต็ม 1 ถึง N จัดเรียงเป็นอาร์เรย์ ถ้าทุกตำแหน่ง i (1≤i≤N) ต้องเป็นจริงอย่างน้อย 1 ข้อ:

• ตัวเลขที่ตำแหน่ง i หาร i ลงตัว
• i หารตัวเลขที่ตำแหน่ง i ลงตัว

ตัวอย่าง: N = 2 → 2 วิธี: [1,2] และ [2,1]

วิธีแก้ปัญหา (Backtracking + Pruning)

1. ฟังก์ชัน solve(visited, end, pos=1):
   • ถ้า pos = end+1 → เพิ่ม ans, return
   • วน i = 1 ถึง end:
     • ถ้า i ยังไม่ถูกใช้ และ (pos%i==0 หรือ i%pos==0):
       • ทำเครื่องหมาย i ใช้แล้ว
       • solve(visited, end, pos+1)
       • ยกเลิกเครื่องหมาย i
2. จาก main: ans=0, visited array, เรียก solve(visited, N), คืน ans

ตัวอย่างโค้ด C++

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

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

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

Input

2

Output

2