นับ Beautiful Arrangement ของตัวเลข 1 ถึง n ใน JavaScript

Beautiful Arrangement

จัดเรียงตัวเลข 1 ถึง num ให้ที่ i (1-indexed) ต้องเป็นจริงอย่างใดอย่างหนึ่ง:

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

ปัญหา

นับจำนวน Beautiful Arrangement ทั้งหมดสำหรับ num ที่กำหนด

ตัวอย่าง

const input = 2

Arrangements: [1,2] และ [2,1] → ผลลัพธ์ 2

โค้ดตัวอย่าง (Backtracking + Bitmask)

const num = 4; 
const countArrangements = (num = 1) => { 
  let ans = 0; 
  const recur = (curr, vis) => { 
    if (curr === 1){ ans++; } 
    else { 
      for (let i = num; i; i--) { 
        let possible = (i % curr === 0 || curr % i === 0); 
        let visited = vis & 1 << i; 
        if (possible && !visited){ recur(curr-1, vis | 1 << i); } 
      } 
    } 
  }; 
  recur(num, 0); 
  return ans; 
}; 
console.log(countArrangements(num));

คำอธิบาย

ใช้ Recursive Backtracking พร้อม Bitmask ติดตามตัวเลขที่ใช้แล้ว