পাইথনে একটি সংখ্যা {A, B} সেট থেকে বেছে নেওয়া পূর্ণসংখ্যাগুলোর যোগফল হিসেবে প্রকাশ করা সম্ভব কিনা তা যাচাই করা

মান লিজিয়ে আমাদের একটি সংখ্যা target আছে। আরো দুটি সংখ্যা A এবং B আছে। আমাদের যাচাই করতে হবে A এবং B যতবার ইচ্ছে যোগ করে target পাওয়া যায় কিনা।

যেমন, ইনপুট যদি Target = 26, A = 5, B = 7 হয়, তবে আউটপুট হবে True কারণ (৭ + ৭ + ৭ + ৫) করে ২৬ পাওয়া যায়।

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

একটি util() ফাংশন সংজ্ঞায়িত করুন। এটি x, a, b, is_ok, target নেবে
যদি x > target হয়, তবে:
- রিটার্ন করুন
যদি is_ok[x] সত্য হয়, তবে:
- রিটার্ন করুন
is_ok[x] := True
util(x + a, a, b, is_ok, target)
util(x + b, a, b, is_ok, target)
মূল মেথড থেকে নিচের কাজ করুন:
- is_ok := সাইজ (target + 1) এর একটি অ্যারে False দিয়ে ভরুন
- util(0, a, b, is_ok, target)
- is_ok[target] রিটার্ন করুন

উদাহরণ

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

def util(x, a, b, is_ok, target):
    if x > target:
        return
    if is_ok[x]:
        return
    is_ok[x] = True
    util(x + a, a, b, is_ok, target)
    util(x + b, a, b, is_ok, target)

def solve(target, a, b):
    is_ok = [False] * (target + 1)
    util(0, a, b, is_ok, target)
    return is_ok[target]

target = 26
A = 5
B = 7
print(solve(target, A, B))

ইনপুট

26, 5, 7

আউটপুট

True