সাবসেট সম সমস্যা

এই সমস্যায়, একটি দেওয়া সেট আছে কিছু ইন্টিজার এলিমেন্টের সাথে। আরেকটি মানও দেওয়া আছে, আমাদের দেওয়া সেটের একটি সাবসেট বের করতে হবে যার যোগফল দেওয়া সম ভ্যালুর সমান।

এখানে ব্যাকট্র্যাকিং অ্যাপ্রোচ ব্যবহার করা হয়েছে একটি বৈধ সাবসেট সিলেক্ট করার চেষ্টায়, যখন একটি আইটেম বৈধ নয়, তখন পুরনো সাবসেটে ফিরে (backtrack) অন্য এলিমেন্ট যোগ করে সমাধান পাওয়া হয়।

ইনপুট এবং আউটপুট

ইনপুট: এই অ্যালগরিদম একটি নাম্বার সেট এবং একটি সম ভ্যালু নেয়। The Set: {10, 7, 5, 18, 12, 20, 15} The sum Value: 35 আউটপুট: দেওয়া সেটের সব সম্ভাব্য সাবসেট, যেখানে প্রতিটি সাবসেটের এলিমেন্টের যোগফল দেওয়া সম ভ্যালুর সমান। {10, 7, 18} {10, 5, 20} {5, 18, 12} {20, 15}

অ্যালগরিদম

subsetSum(set, subset, n, subSize, total, node, sum)

ইনপুট - দেওয়া সেট এবং সাবসেট, সেট এবং সাবসেটের সাইজ, সাবসেটের টোটাল, সাবসেটে এলিমেন্ট সংখ্যা এবং দেওয়া সম।

আউটপুট - সব সম্ভাব্য সাবসেট যাদের যোগফল দেওয়া সমের সমান।

শুরু
  যদি total = sum, তবে
    সাবসেট ডিসপ্লে করুন
    //নেক্সট সাবসেট খুঁজতে যান
    subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
    রিটার্ন
  অন্যথায়
    সেটের সব এলিমেন্ট i-এর জন্য করুন
      subset[subSize] := set[i]
      subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
    শেষ
শেষ

উদাহরণ

#include <iostream> using namespace std; void displaySubset(int subSet[], int size) { for(int i = 0; i < size; i++) { cout << subSet[i] << "  "; } cout << endl; } void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) { if( total == sum) { displaySubset(subSet, subSize); //সাবসেট প্রিন্ট করুন subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum); //অন্যান্য সাবসেটের জন্য return; }else { for( int i = nodeCount; i < n; i++ ) { //ব্রেডথ অনুযায়ী নোড খুঁজুন subSet[subSize] = set[i]; subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum); //ডেপথ অনুযায়ী নেক্সট নোডের জন্য করুন } } } void findSubset(int set[], int size, int sum) { int *subSet = new int[size]; //subsetSum-এ পাস করার জন্য সাবসেট অ্যারে তৈরি করুন subsetSum(set, subSet, size, 0, 0, 0, sum); delete[] subSet; } int main() { int weights[] = {10, 7, 5, 18, 12, 20, 15}; int size = 7; findSubset(weights, size, 35); }

আউটপুট

10 7 18 10 5 20 5 18 12 20 15