আমরা পাইথনে সমান যোগফল দিয়ে দুটি পার্টিশনের গ্রুপ করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম?

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে, আমাদের পরীক্ষা করতে হবে যে আমরা দুটি গ্রুপে ভাগ করতে পারি কিনা যেখানে উভয় গ্রুপের উপাদানের যোগফল একই।

সুতরাং, যদি ইনপুটটি nums =[2, 3, 6, 5] এর মত হয়, তাহলে আউটপুটটি True হবে, যেমন আমরা গ্রুপের মতো করতে পারি:[2, 6] এবং [3, 5]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

• মোট :=সংখ্যায় সমস্ত উপাদানের যোগফল

• যদি মোট বিজোড় হয়, তাহলে

  • রিটার্ন ফলস

• অর্ধেক :=মোটের পূর্ণসংখ্যা অংশ / 2

• dp :=অর্ধেক + 1 আকারের একটি তালিকা এবং মিথ্যা দিয়ে পূরণ করুন

• dp[0] :=সত্য

• প্রতিটি সংখ্যার জন্য, করুন

  • আমি অর্ধেক থেকে 0 রেঞ্জের জন্য, 1 দ্বারা হ্রাস করুন, করুন

    • যদি i>=সংখ্যা হয়, তাহলে

      • dp[i] :=dp[i] বা dp[i - num]

• dp[অর্ধেক]

  ফেরত দিন

উদাহরণ

class Solution:
   def solve(self, nums):

      total = sum(nums)

      if total & 1:
         return False

      half = total // 2

      dp = [True] + [False] * half
      for num in nums:
         for i in range(half, 0, -1):
            if i >= num:
               dp[i] |= dp[i - num]

      return dp[half]

ob = Solution()
nums = [2, 3, 6, 5]
print(ob.solve(nums))

ইনপুট

[2, 3, 6, 5]

আউটপুট

True