মডিউল ১৯_৭ঃ Count Subset Sum with given difference

আমরা এখন আরো একটি ভেরিয়েশন দেখবো যেখানে আমাদেরকে একটা ভ্যালু দেওয়া থাকবে এবং একটি এ্যারে দেওয়া থাকবে। ওই এ্যারে থেকে এমন ভাবে দুইটা সাবসেট বানাইতে হবে যাতে করে সেই সাবসেট দুইটার সাম এর ডিফারেন্স ওই ভ্যালু এর সমান হয়।

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

dif = 1

তাহলে আমরা যদি {1,1,2},{3} এই দুইটা সাবসেট বানায় তাহলে তাদের সাম এর ডিফারেন্স হবে ৪-৩ = ১ যা আমাদের দেওয়া dif এর সমান।

এখন তাহলে ভাবা যাক এটা কিভাবে করা যায়। একটু চিন্তা করলেই আমরা বুঝে যাবো।

ধরি প্রথম সাবসেট এর সাম= s1

দ্বিতীয় সাবসেট এর সাম = s2

তাহলে প্রশ্নমতে, s1-s2 = dif ... ... ... ... ... ...(1)

আবার পুরো এ্যারে এর সাম = totalsum

তার মানে s1+s2 = totalsum ... ... ... ... .... ...(2)

তাহলে আমরা যদি (১)+(২) করি,

2s1 = totalsum + dif

s1 = (totalsum+dif)/2

তাহলে আমরা আমাদের গিবেন ভ্যালু থেকে s1 কয়ভাবে বানানো যায় যদি বের করি তাহলে আমরা আমাদের আন্সার পেয়ে যাবো।

কারন যতভাবে s1 বানানো যায় ঠিক তার অপর ভ্যালু গুলো নিয়ে s2 বানানো সম্ভব। এইতো হয়ে গেলো প্রবলেম সলভ। আশা করি এটার কোডটা তোমরা নিজেরাই করে ফেলতে পারবা।