सबसेट योग समस्या

इस समस्या में, कुछ पूर्णांक तत्वों के साथ एक दिया हुआ समुच्चय होता है। और दूसरा कुछ मान भी दिया गया है, हमें दिए गए समुच्चय का एक उपसमुच्चय ज्ञात करना है जिसका योग दिए गए योग मान के समान है।

यहां बैकट्रैकिंग दृष्टिकोण का उपयोग एक मान्य उपसमुच्चय का चयन करने का प्रयास करने के लिए किया जाता है जब कोई आइटम मान्य नहीं होता है, हम पिछले उपसमुच्चय को प्राप्त करने के लिए पीछे हटेंगे और समाधान प्राप्त करने के लिए एक और तत्व जोड़ेंगे।

इनपुट और आउटपुट

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);
}

आउटपुट