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

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

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

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

इनपुट: यह एल्गोरिदम संख्याओं का एक सेट, और एक योग मान लेता है। सेट: {10, 7, 5, 18, 12, 20, 15} योग मान: 35 आउटपुट: दिए गए सेट के सभी संभावित सबसेट, जहां प्रत्येक सबसेट के प्रत्येक तत्व का योग दिए गए योग मान के समान है। {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  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); }

आउटपुट

10 7 18 10 5 20 5 18 12 20 15