Chương trình đếm số hoán vị mà tổng các cặp liền kề là số chính phương trong Python

Cho danh sách nums, đếm số hoán vị sao cho tổng mọi cặp phần tử liền kề là số chính phương. Hai hoán vị khác nhau nếu tồn tại chỉ số i mà A[i] != B[i].

Ví dụ: nums = [2, 9, 7] → 2 hoán vị: [2, 7, 9] và [9, 7, 2].

Giải pháp

Backtracking với cắt tỉa:

• Duyệt tất cả hoán vị bằng cách swap
• Khi đặt phần tử tại vị trí i+1, kiểm tra nums[i] + nums[j] có phải số chính phương không
• Dùng set visited để tránh thử cùng một giá trị sum nhiều lần tại cùng cấp độ
• Đệ quy util(i): nếu i+1 == n thì tìm thấy 1 hoán vị hợp lệ

Ví dụ minh họa

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))

Đầu vào

[2, 9, 7]

Đầu ra

2