পাইথনে অ্যারে সম K করার জন্য তিন অপারেশন একবার করে সম্ভব কিনা

একটি অ্যারে nums এবং মান K দেওয়া আছে। প্রতিটি এলিমেন্টে শুধু একবার নিচের অপারেশনগুলো করতে পারবেন:

1. এলিমেন্টকে নেগেটিভ করুন।
2. ইন্ডেক্স (১-বেজড) যোগ করুন।
3. ইন্ডেক্স বিয়োগ করুন।

অ্যারেটির সম K করা সম্ভব কিনা যাচাই করুন।

উদাহরণ

ইনপুট: nums = [1,2,3,7], K = 8

আউটপুট: True

ব্যাখ্যা: ২ এবং ৩ থেকে তাদের ইন্ডেক্স বিয়োগ করলে অ্যারে হয় [1,0,0,7], যোগফল ৮।

অ্যালগরিদম (DP + মেমোইজেশন)

1. রিকার্সিভ ফাংশন is_ok(i, total, K, nums, table)।
2. প্রতিটি ইন্ডেক্সে তিন অপারেশন + কিছু না করা (৪ অপশন) ট্রাই করুন।
3. টেবিল দিয়ে ওভারল্যাপিং সাবপ্রব্লেম এড়িয়ে চলুন।

উদাহরণ কোড

size = 100

def is_ok(i, total, k, nums, table):
    n = len(nums)
    if total <= 0:
        return False
    if i >= n:
        return total == k
    if table[i][total] != -1:
        return table[i][total]
    table[i][total] = (is_ok(i+1, total - 2*nums[i], k, nums, table) or
                       is_ok(i+1, total, k, nums, table))
    table[i][total] = (is_ok(i+1, total - (i+1), k, nums, table) or
                       table[i][total])
    table[i][total] = (is_ok(i+1, total + i + 1, k, nums, table) or
                       table[i][total])
    return table[i][total]

def solve(nums, k):
    total = sum(nums)
    table = [[-1]*size for _ in range(size)]
    return is_ok(0, total, k, nums, table)

nums = [1, 2, 3, 7]
k = 8
print(solve(nums, k))  # Output: True

ইনপুট

[1,2,3,7], 8

আউটপুট

True