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 }
50
1def SubsetSum(set, n, sum) :
2 # Base Cases
3 if (sum == 0) :
4 return True
5 if (n == 0 and sum != 0) :
6 return False
7 # ignore if last element is > sum
8 if (set[n - 1] > sum) :
9 return SubsetSum(set, n - 1, sum);
10 # else,we check the sum
11 # (1) including the last element
12 # (2) excluding the last element
13 return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sumset[n-1])
14# main
15set = [2, 14, 6, 22, 4, 8]
16sum = 10
17n = len(set)
18if (SubsetSum(set, n, sum) == True) :
19 print("Found a subset with given sum")
20else :
21 print("No subset with given sum")