উপসেট সমষ্টি সমস্যা

এই সমস্যায়, কিছু পূর্ণসংখ্যা উপাদান সহ একটি প্রদত্ত সেট রয়েছে৷ এবং আরেকটি কিছু মানও দেওয়া আছে, আমাদের প্রদত্ত সেটের একটি উপসেট খুঁজে বের করতে হবে যার যোগফল প্রদত্ত যোগফলের মানের সমান।

এখানে ব্যাকট্র্যাকিং পদ্ধতি একটি বৈধ উপসেট নির্বাচন করার চেষ্টা করার জন্য ব্যবহার করা হয় যখন একটি আইটেম বৈধ নয়, আমরা পূর্ববর্তী উপসেট পেতে ব্যাকট্র্যাক করব এবং সমাধান পেতে অন্য একটি উপাদান যোগ করব৷

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

Input:
This algorithm takes a set of numbers, and a sum value.
The Set: {10, 7, 5, 18, 12, 20, 15}
The sum Value: 35
Output:
All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value.
{10,  7,  18}
{10,  5,  20}
{5,  18,  12}
{20,  15}

অ্যালগরিদম

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

ইনপুট - প্রদত্ত সেট এবং উপসেট, সেট এবং উপসেটের আকার, উপসেটের মোট, উপসেটের উপাদানগুলির সংখ্যা এবং প্রদত্ত যোগফল৷

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

Begin
   if total = sum, then
      display the subset
      //go for finding next subset
      subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
      return
   else
      for all element i in the set, do
         subset[subSize] := set[i]
         subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
      done
End

উদাহরণ

#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);     //print the subset
      subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     //for other subsets
      return;
   }else {
      for( int i = nodeCount; i < n; i++ ) {     //find node along breadth
         subSet[subSize] = set[i];
         subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);     //do for next node in depth
      }
   }
}

void findSubset(int set[], int size, int sum) {
   int *subSet = new int[size];     //create subset array to pass parameter of 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);
}

আউটপুট