โปรแกรมนับจำนวนการเรียงสับเปลี่ยนที่ผลรวมคู่ติดกันเป็นกำลังสองใน Python

คำอธิบายโจทย์

ให้รายการ nums หาจำนวน permutation ที่ผลรวมของทุกคู่ติดกันเป็น perfect square (กำลังสองสมบูรณ์)

ตัวอย่าง

nums = [2, 9, 7] → เอาต์พุต: 2 ([2,7,9] และ [9,7,2])

วิธีแก้ปัญหา

Backtracking + Pruning:

1. สร้าง permutation ทีละตัวโดย swap
2. ตอนวางตัวที่ i+1: ลองทุก j > i ที่ nums[i] + nums[j] เป็น perfect square
3. ใช้ visited set ป้องกันลองค่า sum ซ้ำในระดับเดียวกัน (pruning สำคัญ)
4. นับ permutation ที่สมบูรณ์

โค้ด Python

from math import sqrt

class Solution:
    def solve(self, nums):
        self.res = 0
        
        def util(i):
            if i + 1 == len(nums):
                self.res += 1
                return
            visited = set()
            for j in range(i + 1, len(nums)):
                s = nums[i] + nums[j]
                if s not in visited and int(sqrt(s)) ** 2 == s:
                    visited.add(s)
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
                    util(i + 1)
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
        
        visited = set()
        for i in range(len(nums)):
            nums[i], nums[0] = nums[0], nums[i]
            if nums[0] not in visited:
                util(0)
            visited.add(nums[0])
            nums[i], nums[0] = nums[0], nums[i]
        
        return self.res

ob = Solution()
nums = [2, 9, 7]
print(ob.solve(nums))

อินพุต

[2, 9, 7]

เอาต์พุต

2