subset sum problem backtracking code example

Example 1: subset sum problem using backtracking in c++

/* Part of Cosmos by OpenGenus Foundation */
    #include<iostream>
    using namespace std;
    /*
    *Find whether or not there exists any subset 
    *  of array  that sum up to targetSum
    */
    class Subset_Sum
    {
        public:
        // BACKTRACKING ALGORITHM
        void subsetsum_Backtracking(int Set[] , int pos, int sum, int tmpsum, int size, bool & found)
        {
            if (sum == tmpsum)
                found = true;
                // generate nodes along the breadth
            for (int i = pos; i < size; i++)
            {
             if (tmpsum + Set[i] <= sum)
               {
                  tmpsum += Set[i];   
                  // consider next level node (along depth)
                  subsetsum_Backtracking(Set, i + 1, sum, tmpsum, size, found);
                  tmpsum -= Set[i];
                }
            }
        }
    };
    
    int main()
    {
        int i, n, sum;
        Subset_Sum S;
        cout << "Enter the number of elements in the set" << endl;
        cin >> n;
        int a[n];
        cout << "Enter the values" << endl;
        for(i=0;i<n;i++)
          cin>>a[i];
        cout << "Enter the value of sum" << endl;
        cin >> sum;
        bool f = false;
        S.subsetsum_Backtracking(a, 0, sum, 0, n, f);
        if (f)
           cout << "subset with the given sum found" << endl;
        else
           cout << "no required subset found" << endl;   
        return 0;
    }

Example 2: subset sum problem using backtracking python

def SubsetSum(set, n, sum) :
   # Base Cases
   if (sum == 0) :
      return True
   if (n == 0 and sum != 0) :
      return False
   # ignore if last element is > sum
   if (set[n - 1] > sum) :
      return SubsetSum(set, n - 1, sum);
   # else,we check the sum
   # (1) including the last element
   # (2) excluding the last element
   return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sumset[n-1])
# main
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (SubsetSum(set, n, sum) == True) :
   print("Found a subset with given sum")
else :
   print("No subset with given sum")

Example 3: sum of subset problem using backtracking in c

#include<stdio.h>#include<conio.h>#define TRUE 1#define FALSE 0int inc[50],w[50],sum,n;int promising(int i,int wt,int total) {	return(((wt+total)>=sum)&&((wt==sum)||(wt+w[i+1]<=sum)));}/** You can find this program on GitHub * https://github.com/snadahalli/cprograms/blob/master/subsets.c*/void main() {	int i,j,n,temp,total=0;	clrscr();	printf("\n Enter how many numbers:\n");	scanf("%d",&n);	printf("\n Enter %d numbers to th set:\n",n);	for (i=0;i<n;i++) {		scanf("%d",&w[i]);		total+=w[i];	}	printf("\n Input the sum value to create sub set:\n");	scanf("%d",&sum);	for (i=0;i<=n;i++)	  for (j=0;j<n-1;j++)	   if(w[j]>w[j+1]) {		temp=w[j];		w[j]=w[j+1];		w[j+1]=temp;	}	printf("\n The given %d numbers in ascending order:\n",n);	for (i=0;i<n;i++)	  printf("%d \t",w[i]);	if((total<sum))	  printf("\n Subset construction is not possible"); else {		for (i=0;i<n;i++)		   inc[i]=0;		printf("\n The solution using backtracking is:\n");		sumset(-1,0,total);	}	getch();}void sumset(int i,int wt,int total) {	int j;	if(promising(i,wt,total)) {		if(wt==sum) {			printf("\n{\t");			for (j=0;j<=i;j++)			    if(inc[j])			     printf("%d\t",w[j]);			printf("}\n");		} else {			inc[i+1]=TRUE;			sumset(i+1,wt+w[i+1],total-w[i+1]);			inc[i+1]=FALSE;			sumset(i+1,wt,total-w[i+1]);		}	}}