পাইথনে आसন্ন জোড়ার যোগফল পূর্ণবর্গ হলে পারমুটেশন গণনা

একটি সংখ্যার লিস্ট nums দেওয়া আছে। আমাদের এমন পারমুটেশনগুলো গণনা করতে হবে যেখানে প্রতিটি আসন্ন জোড়ার (Adjacent Pair) যোগফল একটি পূর্ণবর্গ (Perfect Square) হয়। দুটি পারমুটেশন স্বতন্ত্র হবে যদি কোনো ইনডেক্সে তাদের মান আলাদা হয়।

উদাহরণ: nums = [2, 9, 7] → আউটপুট 2 ([2, 7, 9] এবং [9, 7, 2])।

সমাধানের ধাপসমূহ (ব্যাকট্র্যাকিং + প্রুনিং)

res := 0
util(i) ফাংশন:
- যদি i+1 == len(nums), তবে res++ এবং রিটার্ন।
- visited সেট রাখুন যাতে একই যোগফল বারবার চেক না হয়।
- j = i+1 থেকে শেষ পর্যন্ত:
  - s = nums[i] + nums[j]
  - যদি s ভিজিটেড না হয় এবং পূর্ণবর্গ হয়, তবে:
    - s ভিজিটেড মার্ক করুন।
    - nums[i+1] এবং nums[j] সোয়াপ করুন।
    - util(i+1) কল করুন।
    - ব্যাকট্র্যাক (সোয়াপ ফেরত দিন)।
মেইন থেকে প্রতিটি উপাদানকে প্রথমে আনোয়া করে util(0) কল করুন (ডুপ্লিকেট এড়াতে visited সেট ব্যবহার করুন)।
res রিটার্ন করুন।

পাইথন কোড উদাহরণ

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]