Light OJ - 1235 - Coin Change (IV) - Tutorial
Topic of this problem: Binary Search with "meet in the middle" tricks মিট ইন দ্য মিডল টেকনিক হলো প্রব্লেম টা কে দুইভাগে ভাগ করে সেই দুই ভাগের রেজাল্ট মার্জ করে ফাইনাল রেজাল্ট টা বের করা। ১। এই প্রব্লেমে কয়েন সংখ্যা মাত্র n = ১৮ টি। প্রত্যেক কয়েন সর্বোচ্চ দুইবার নেয়া যায়। ২। প্রব্লেম সলভের আইডিয়া হলো কয়েনগুলোকে দুইভাগে ভাগ করে নেবো। এরপর প্রথম ভাগের অল পসিবল সাবসেট এর জন্য যতো ভ্যালু বানানো যায় তা একটি ভেক্টরে পুশ করবো। ৩। এরপর একইভাবে ২য় ভাগের কয়েনগুলোর অল পসিবল সাবসেট এর জন্য যে যে ভ্যালু X বানানো যায় প্রথমভাগে বাইনারী সার্চ চালিয়ে দেখবো K-X আছে কি না। যদি থাকে তার মানে K ভ্যালু বানানো যাবে এই কয়েনগুলো দিয়ে। ৪। অল পসিবল সাবসেট জেনারেট করার সময় যেকোন একটা কয়েন আমি চাইলে ০ বার, ১বার অথবা ২ বার নিতে পারি। অনুরূপ একটি প্রব্লেম হলো Funny Knapsack মিট ইন দ্য মিডল সম্পর্কে আরো জানতে Tap The Link -_-