Advertisement
Farid_Mia59

found or not

Nov 16th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement