জাভাস্ক্রিপ্টে টার্গেট সমষ্টি পাওয়ার সব সম্ভাব্য কম্বিনেশন বের করা

সমস্যা বিবরণ

নাম্বার অ্যারে এবং একটি টার্গেট সমষ্টি দেওয়া আছে। অ্যারে থেকে নম্বর বেছে নেওয়া (রিপিটอลো 허용) যাতে সমষ্টি টার্গেটের সমান হয়। সব সম্ভাব্য কম্বিনেশন রিটার্ন করতে হবে।

ইনপুট: arr = [14, 6, 10], sum = 40

আউটপুট: [[14,14,6,6], [14,6,10,10], [6,6,6,6,6,10], [10,10,10,10]]

সমাধান (ব্যাকট্র্যাকিং)

const arr = [14, 6, 10];
const sum = 40;

const findSum = (arr, sum) => {
  const res = [];
  const search = (index, part = []) => {
    const s = part.reduce((a, b) => a + b, 0);
    if (s === sum) { res.push(part); }
    if (s >= sum || index >= arr.length) return;
    search(index, part.concat(arr[index]));   // এই নম্বর আবার নাও
    search(index + 1, part);                  // পরের নম্বরে যাও
  };
  search(0);
  return res;
};

console.log(findSum(arr, sum));

আউটপুট

[
  [ 14, 14, 6, 6 ],
  [ 14, 6, 10, 10 ],
  [ 6, 6, 6, 6, 6, 10 ],
  [ 10, 10, 10, 10 ]
]

ব্যাখ্যা

• রিকার্সিভ ব্যাকট্র্যাকিং: প্রতিটি ধাপে দুটি চয়েস - বর্তমান নম্বর আবার নাও, অথবা পরের নম্বরে যাও।
• part.concat দিয়ে নতুন অ্যারে তৈরি করা হয় (ইমিউটেবল অ্যাপ্রোচ)।
• বেস কেস: সমষ্টি টার্গেটের সমান হলে পুশ, বড় হলে বা অ্যারে শেষ হলে রিটার্ন।