ধরুন, আমাদের কাছে ডুপ্লিকেট ছাড়া একটি ক্যান্ডিডেট নম্বারের সেট এবং একটি টার্গেট নম্বর (target) আছে।
আমাদের একটি ফাংশন লিখতে হবে যা ক্যান্ডিডেটগুলোর মধ্যে যেসব ইউনিক কম্বিনেশনের যোগফল টার্গেটের সমান তা বের করবে।
একই নম্বর ক্যান্ডিডেটগুলোর থেকে অনলিমিটেড বার বেছে নেওয়া যাবে।
নোট:
সব নম্বর (টার্গেটসহ) পজিটিভ ইন্টিজার হবে।
সমাধান সেটে ডুপ্লিকেট কম্বিনেশন থাকবে না।
উদাহরণ:
যদি ইনপুট হয়:
candidates = [2,3,6,7], target = 7,
তাহলে সমাধান হতে পারে:
[ [7], [2,2,3] ];
যেহেতু সমস্যাটি সব সম্ভাব্য ফলাফল বের করার, সেরা বা সংখ্যা বের করার নয়, তাই ডাইনামিক প্রোগ্রামিং দরকার নেই, রিকার্সিভ ব্যাকট্র্যাকিং পদ্ধতিই যথেষ্ট।
উদাহরণ
নিচে কোডটি দেওয়া হলো:
const recursiveSum = ( candidates, remainingSum, finalCombinations = [], currentCombination = [], startFrom = 0, ) => { if (remainingSum < 0) { return finalCombinations; } if (remainingSum === 0) { finalCombinations.push(currentCombination.slice()); return finalCombinations; } for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) { const currentCandidate = candidates[candidateIndex]; currentCombination.push(currentCandidate); recursiveSum( candidates, remainingSum - currentCandidate, finalCombinations, currentCombination, candidateIndex, ); currentCombination.pop(); } return finalCombinations; } const combinationSum = (candidates, target) => recursiveSum(candidates, target); console.log(combinationSum([2, 3, 6, 7], 7));আউটপুট
কনসোলে নিচের আউটপুট পাওয়া যাবে:
[ [ 2, 2, 3 ], [ 7 ] ]
