SHARE
TWEET

found or not

Farid_Mia59 Nov 16th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     /* Part of Cosmos by OpenGenus Foundation */
  2.     #include<iostream>
  3.     using namespace std;
  4.     /*
  5.     *Find whether or not there exists any subset
  6.     *  of array  that sum up to targetSum
  7.     */
  8.     class Subset_Sum
  9.     {
  10.         public:
  11.         // BACKTRACKING ALGORITHM
  12.         void subsetsum_Backtracking(int Set[] , int pos, int sum, int tmpsum, int size, bool & found)
  13.         {
  14.             if (sum == tmpsum)
  15.                 found = true;
  16.                 // generate nodes along the breadth
  17.             for (int i = pos; i < size; i++)
  18.             {
  19.              if (tmpsum + Set[i] <= sum)
  20.                {
  21.                   tmpsum += Set[i];
  22.                   // consider next level node (along depth)
  23.                   subsetsum_Backtracking(Set, i + 1, sum, tmpsum, size, found);
  24.                   tmpsum -= Set[i];
  25.                 }
  26.             }
  27.         }
  28.     };
  29.  
  30.     int main()
  31.     {
  32.         int i, n, sum;
  33.         Subset_Sum S;
  34.         cout << "Enter the number of elements in the set" << endl;
  35.         cin >> n;
  36.         int a[n];
  37.         cout << "Enter the values" << endl;
  38.         for(i=0;i<n;i++)
  39.           cin>>a[i];
  40.         cout << "Enter the value of sum" << endl;
  41.         cin >> sum;
  42.         bool f = false;
  43.         S.subsetsum_Backtracking(a, 0, sum, 0, n, f);
  44.         if (f)
  45.            cout << "subset with the given sum found" << endl;
  46.         else
  47.            cout << "no required subset found" << endl;
  48.         return 0;
  49.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top