Sum of Sub-Sets Problem using Backtracking - BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Sum of Sub-Sets Problem using Backtracking

Share This
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 includes x and whose sum is T.
  • There is a subset of X that excludes x and whose sum is T.
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; }

 Happy Exploring!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.