• API
• FAQ
• Tools
• Archive
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.

Top