মডিউল ১৯_৮ঃ Target Sum

আমরা এখন লাস্ট আরেকটা ভেরিয়েশন দেখবো। এখানে আমাদের একটা এ্যারে দেওয়া থাকবে আর একটা target দেওয়া থাকবে। এ্যারে এর আগে পরে + বা - বসিয়ে আমরা target বানাইতে পারবো কিনা এটা বের করতে হবে।

ধরি A = {1,1,2,3}

target = 1

আমরা 1+1+2-3 = 1

1-1+2-3 = |-1| = 1

পেতে পারি। তাহলে এবার একটা জিনিস একটু খেয়াল করি। আমরা প্লাস এর সংখ্যা গুলোকে একপাশে নেই আর মাইনাস এর সংখ্যা গুলোকে এক পাশে নেই।

(1+2)-(1+3) = abs(1) হয়।

তাহলে আবার একটু খেয়াল করে দেখো আমরা যদি প্লাস এর এলিমেন্ট গুলোকে একটা সাবসেট কল্পনা করি আর মাইনাস এর এলিমেন্ট গুলোকে আরেকটা সাবসেট কল্পনা করি তাহলে এটা আমাদের আগের শেখা Count Subset with given difference এর মতো হয়ে যাচ্ছে।

তাহলে এখানেও s1 = (totalsum+target)/2

তবে এখানে খেয়াল রাখতে হবে যে totalsum+target কে যদি ২ দিয়ে ভাগ করা না যায় তাহলে আমরা আসলে target বানাইতে পারবো না।

একটা উদাহরন এর সাহায্যে এটা একটু বোঝার চেষ্টা করি ধরি,

A = {1,1,2,3},Sum = 7

target = 2

তাহলে এখানে খেয়াল করে দেখো কোনো ভাবেই তুমি প্লাস মাইনাস বসিয়ে ২ আনতে পারবা না।

তাই অবশ্যই totalsum+target ২ দিয়ে বিভাজ্য হতে হবে।