Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
Sum of Subsets problem
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Here backtracking approach is used for trying to select 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.
Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True There is a subset (4, 5) with sum 9. Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30 Output: False There is no subset that add up to 30.
Method 1: Recursion.
Approach: For the recursive approach we will consider two cases.
- Consider the last element and now the required sum = target sum – value of ‘last’ element and number of elements = total elements – 1
- Leave the ‘last’ element and now the required sum = target sum and number of elements = total elements – 1
Following is the recursive formula for isSubsetSum() problem.
isSubsetSum(set, n, sum)
= isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0
Let’s take a look at the simulation of above approach-:
set[]={3, 4, 5, 2}
sum=9
(x, y)= 'x' is the left number of elements,
'y' is the required sum
(4, 9)
{True}
/ \
(3, 6) (3, 9)
/ \ / \
(2, 2) (2, 6) (2, 5) (2, 9)
{True}
/ \
(1, -3) (1, 2)
{False} {True}
/ \
(0, 0) (0, 2)
{True} {False}
Implementation:
// A recursive solution for subset sum problem
#include <stdio.h>
// Returns true if there is a subset
// of set[] with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained by any
of the following:
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
// Driver program to test above function
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
Output:
Found a subset with given sum
Example:
Input and Output
Input: This algorithm takes a set of numbers, and a sum value. The Set: {10, 7, 5, 18, 12, 20, 15} The sum Value: 35 Output: All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value. {10, 7, 18} {10, 5, 20} {5, 18, 12} {20, 15}
Algorithm
subsetSum(set, subset, n, subSize, total, node, sum)
Input − The given set and subset, size of set and subset, a total of the subset, number of elements in the subset and the given sum.
Output − All possible subsets whose sum is the same as the given sum.
Begin
if total = sum, then
display the subset
//go for finding next subset
subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
return
else
for all element i in the set, do
subset[subSize] := set[i]
subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
done
End
Implementation:
#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) {
displaySubset(subSet, subSize); //print the subset
subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum); //for other subsets
return;
}else {
for( int i = nodeCount; i < n; i++ ) { //find node along breadth
subSet[subSize] = set[i];
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum); //do for next node in depth
}
}
}
void findSubset(int set[], int size, int sum) {
int *subSet = new int[size]; //create subset array to pass parameter of subsetSum
subsetSum(set, subSet, size, 0, 0, 0, sum);
delete[] subSet;
}
int main() {
int weights[] = {10, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
Output:
10 7 18
10 5 20
5 18 12
20 15