Example 1: subset sum problem using backtracking in c++
#include<iostream>
using namespace std;
class Subset_Sum
{
public:
void subsetsum_Backtracking(int Set[] , int pos, int sum, int tmpsum, int size, bool & found)
{
if (sum == tmpsum)
found = true;
for (int i = pos; i < size; i++)
{
if (tmpsum + Set[i] <= sum)
{
tmpsum += Set[i];
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)));}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]); } }}