পাইথনে সিম্বল अरেঞ্জ করে টার্গেট পাওয়ার উপায়ের সংখ্যা বের করার প্রোগ্রাম

ধরা যাক nums নামক একটি নন-নেগেটিভ সংখ্যার লিস্ট এবং একটি ইন্টিজার target দেওয়া আছে। আমাদের nums-এ '+' এবং '-' সিম্বলগুলো সাজাতে হবে যাতে এক্সপ্রেশনটির মান target হয়। এই কাজ কতভাবে করা যায় তা বের করতে হবে।

উদাহরণ

ইনপুট: nums = [2, 3, 3, 3, 2], target = 9

আউটপুট: 2

ব্যাখ্যা: দুটি উপায়: -2 + 3 + 3 + 3 + 2 এবং 2 + 3 + 3 + 3 - 2।

সমাধানের ধাপসমূহ

1. s := nums-এর সব সংখ্যার যোগফল
2. যদি (s + target) % 2 != 0 বা target > s হয়, তবে 0 ফেরত দিন
3. W := (s + target) // 2
4. dp1 := [0] * (W + 1), dp1[0] := 1
5. dp2 := [0] * (W + 1)
6. i = 0 থেকে len(nums)-1 পর্যন্ত:
   • j = 0 থেকে W পর্যন্ত:
     • যদি j >= nums[i] হয়, তবে dp2[j] += dp1[j - nums[i]]
   • j = 0 থেকে W পর্যন্ত:
     • dp1[j] += dp2[j]
     • dp2[j] = 0
7. dp1[-1] (শেষ এলিমেন্ট) ফেরত দিন

পাইথন ইমপ্লিমেন্টেশন

class Solution:
    def solve(self, nums, target):
        s = sum(nums)
        if (s + target) % 2 != 0 or target > s:
            return 0
        W = (s + target) // 2
        dp1 = [0] * (W + 1)
        dp1[0] = 1
        dp2 = [0] * (W + 1)
        for i in range(len(nums)):
            for j in range(W + 1):
                if j >= nums[i]:
                    dp2[j] += dp1[j - nums[i]]
            for j in range(W + 1):
                dp1[j] += dp2[j]
                dp2[j] = 0
        return dp1[-1]

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

ইনপুট

[2, 3, 3, 3, 2], 9

আউটপুট

2