পাইথনে দেওয়া সেটের এলিমেন্টগুলো ব্যবহার করে নির্দিষ্ট সমফল (sum) পাওয়া সম্ভব কিনা তা যাচাই করা

মান লিজিয়ে আমাদের একটি অ্যারে nums এবং আরেকটি ভ্যালু sum আছে। আমাদের যাচাই করতে হবে nums-এ উপস্থিত এলিমেন্টগুলো যোগ করে sum পাওয়া সম্ভব কিনা, আমরা একক এলিমেন্টকে একাধিকবার বেছে নিতে পারি।

যেমন, ইনপুট যদি nums = [2, 3, 5], sum = 28 হয়, তবে আউটপুট হবে True কারণ ৫ + ৫ + ৫ + ৫ + ৩ + ৩ + ২ = ২৮ পাওয়া যায়।

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

MAX := 1000
table := সাইজ MAX একটি অ্যারে ০ দিয়ে ভরুন
util() ফাংশন সংজ্ঞায়িত করুন। এটি nums নেবে
- table[0] := 1
- nums লিস্টটি সর্ট করুন
- i ০ থেকে nums-এর সাইজ - ১ পর্যন্ত, করুন:
  - val := nums[i]
  - যদি table[val] নন-জিরো হয়, তবে:
    - নেক্সট ইটারেশনে যান
  - j ০ থেকে MAX - val - 1 পর্যন্ত, করুন:
    - যদি table[j] নন-জিরো হয়, তবে:
      - table[j + val] := 1
মূল মেথড থেকে নিচের কাজ করুন:
- util(nums)
- যদি table[sum] নন-জিরো হয়, তবে:
  - True রিটার্ন করুন
- False রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

MAX = 1000
table = [0] * MAX

def util(nums):
    table[0] = 1
    nums.sort()
    for i in range(len(nums)):
        val = nums[i]
        if table[val]:
            continue
        for j in range(MAX - val):
            if table[j]:
                table[j + val] = 1

def solve(nums, sum):
    util(nums)
    if table[sum]:
        return True
    return False

nums = [2, 3, 5]
sum = 28
print(solve(nums, sum))

ইনপুট

[2, 3, 5], 28

আউটপুট

True