subset sum problem using backtracking in c 2b 2b

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")