Subset sum problem is the problem of finding a subset such that the sum of elements equal a given number. The backtracking approach generates all permutations in the worst case but in general, performs better than the recursive approach towards subset sum problem.
A subset
X
of n
positive integers and a value sum is given, find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum.In this article, we will solve Subset Sum problem using a backtracking approach which will take
O(2^N)
time complexity but is significantly faster than the recursive approach which take exponential time as well.Example
Given a set
X
of positive integers and target integer T
, is there a subset of elements in X
that add up to T
? Notice that there can be more than one such subset.For example, if
X = {8, 6, 7, 5, 3, 10, 9}
and T = 15
, the answer is TRUE, thanks to the subsets {8, 7}
or {7, 5, 3}
or {6, 9}
or {5, 10}
.On the other hand, if
X = {11,6,5,1,7,13,12}
and T = 15
, the answer is FALSE.Algorithm and Complexity
There are two trivial cases. If the target value
T
is zero, then we can immediately return TRUE, because the elements of the empty set add up to zero. On the other hand, if T < 0
, or if T != 0
but the set X
is empty, then we can immediately return FALSE.For the general case, consider an arbitrary element
x ∈ X
. There is a subset of X
that sums to T
if and only if one of the following statements is true:- There is a subset of
X
that includesx
and whose sum isT
. - There is a subset of
X
that excludesx
and whose sum isT
.
In the first case, there must be a subset of
X \ {x}
that sums to T - x
; in the second case, there must be a subset of X \ {x}
that sums to T
. So we can solve SUBSETSUM(X, T)
by reducing it to two simpler instances: SUBSETSUM(X \ {x}, T - x)
and SUBSETSUM(X \ {x}, T)
. Here's how the resulting recusive algorithm might look if X
is stored in an array.The running time
T(n)
clearly satisfies the recurrence T(n) ≤ 2T(n - 1) + O(1)
, so the running time is T(n) = O(2^n)
by the annihilator method.Here is a similar recursive algorithm that actually constructs a subset of
X
that sums to T
, if one exists. This algorithm also runs in O(2^n)
time.Implementation using C Programming Language
#include <stdio.h>
#define MAX 20 // Maximum number of elements
// Function to print the solution (subset)
void printSubset(int subset[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", subset[i]);
}
printf("\n");
}
// Backtracking function to find subsets that sum up to the target
void sumOfSubsets(int set[], int subset[], int size, int index, int currentSum, int target, int totalRemaining) {
// If the current sum equals the target, print the subset
if (currentSum == target) {
printSubset(subset, index);
return;
}
// If the current sum exceeds the target or no remaining elements can make the sum, return
if (currentSum > target || index == size) {
return;
}
// Iterate over the remaining elements to try including them in the subset
for (int i = index; i < size; i++) {
// If including this element in the current subset doesn't exceed the target sum, proceed
if (currentSum + set[i] <= target) {
subset[index] = set[i]; // Include the element in the subset
sumOfSubsets(set, subset, size, i + 1, currentSum + set[i], target, totalRemaining - set[i]); // Recursive call
}
}
}
// Function to initialize the subset array and call the backtracking function
void findSubsets(int set[], int size, int target) {
int subset[MAX]; // To store the current subset
sumOfSubsets(set, subset, size, 0, 0, target, 0);
}
int main() {
int n, target;
printf("Enter the number of elements in the set: ");
scanf("%d", &n);
int set[MAX];
printf("Enter the elements of the set:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &set[i]);
}
printf("Enter the target sum: ");
scanf("%d", &target);
printf("Subsets that sum to %d are:\n", target);
findSubsets(set, n, target);
return 0;
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.