Subset Sum Problem
Subset Sum Problem
In the sum of subsets problem, there is a given set with some non-negative integer elements. And another sum value is also provided, our task is to find all possible subsets of the given set whose sum is the same as the given sum value.
Set: In mathematical terms, a set is defined as a collection of similar types of objects. The entities or objects of a set must be related to each other through the same rule.
Subset: Suppose there are two sets namely set P and set Q. The set P is said to be a subset of set Q, only if all the elements of set P also belong to the set Q and vice-versa need not be true.
Input Output Scenario
Suppose the given set and sum value is −
Set = {1, 9, 7, 5, 18, 12, 20, 15}
sum value = 35
All possible subsets of the given set, where sum of each element for every subset is the same as the given sum value are given below −
{1 9 7 18}
{1 9 5 20}
{5 18 12}
Backtracking Approach to solve Subset Sum Problem
In the naive method to solve a subset sum problem, the algorithm generates all the possible permutations and then checks for a valid solution one by one. Whenever a solution satisfies the constraints, mark it as a part of the solution.
In solving the subset sum problem, the backtracking approach is used for selecting a valid subset. When an item is not valid, we will backtrack to get the previous subset and add another element to get the solution.
In the worst-case scenario, backtracking approach may generate all combinations, however, in general, it performs better than the naive approach.
Follow the below steps to solve subset sum problem using the backtracking approach −
First, take an empty subset.
Include the next element, which is at index 0 to the empty set.
If the subset is equal to the sum value, mark it as a part of the solution.
If the subset is not a solution and it is less than the sum value, add next element to the subset until a valid solution is found.
Now, move to the next element in the set and check for another solution until all combinations have been tried.
Example
In this example, we are illustrating how to solve the subset sum problem in various programming languages.
#include <stdio.h>
#define SIZE 7
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
printf("%d ", subSet[i]);
}
printf("
");
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
//print the subset
displaySubset(subSet, subSize);
//for other subsets
if (subSize != 0)
subsetSum(set,subSet,n,subSize-2,total-set[nodeCount],nodeCount+1,sum);
return;
}else {
//find node along breadth
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//do for next node in depth
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}
void findSubset(int set[], int size, int sum) {
//create subset array to pass parameter of subsetSum
int subSet[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
}
int main() {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = SIZE;
findSubset(weights, size, 35);
return 0;
}
#include <iostream>
using namespace std;
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
cout << subSet[i] << " ";
}
cout << endl;
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount, int sum) {
if( total == sum) {
//print the subset
displaySubset(subSet, subSize);
//for other subsets
subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1,sum);
return;
}else {
//find node along breadth
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//do for next node in depth
subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);
}
}
}
void findSubset(int set[], int size, int sum) {
//create subset array to pass parameter of subsetSum
int *subSet = new int[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
delete[] subSet;
}
int main() {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
public class Main {
static void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
System.out.print(subSet[i] + " ");
}
System.out.println();
}
static void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
//print the subset
displaySubset(subSet, subSize);
//for other subsets
if (subSize != 0)
subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);
return;
} else {
//find node along breadth
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//do for next node in depth
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}
static void findSubset(int set[], int size, int sum) {
//create subset array to pass parameter of subsetSum
int subSet[] = new int[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
}
public static void main(String[] args) {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
}
def displaySubset(subSet, size):
for i in range(size):
print(subSet[i], end=" ")
print()
def subsetSum(set, subSet, n, subSize, total, nodeCount, sum):
if total == sum:
#print the subset
displaySubset(subSet, subSize)
#for other subsets
if subSize != 0:
subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum)
return
else:
#find node along breadth
for i in range(nodeCount, n):
subSet[subSize] = set[i]
#do for next node in depth
subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum)
def findSubset(set, size, sum):
#create subset array to pass parameter of subsetSum
subSet = [0]*size
subsetSum(set, subSet, size, 0, 0, 0, sum)
if __name__ == "__main__":
weights = [1, 9, 7, 5, 18, 12, 20, 15]
size = 7
findSubset(weights, size, 35)
Output
1 9 7 18 1 9 5 20 5 18 12
