Subset Sum Problem in C
In this article we will learn how to solve the subset sum problem in c programming using recursion method and dynamic programming.
The Subset Sum Problem is fundamentally a decision problem, i.e., For a given set and the target sum, the question is: “Is there a subset of the given set that adds up to the given target sum?“
A company named ‘XYZ’ is planning to launch a marketing campaign through social media, radio, and billboards. The company has a budget of $800 and has a target to reach 15,000 people. The company wants to maximize its reach at this cost by selecting a combination of channels.
Can the company achieve its desired reach within the given budget?
Problem Statement: Find the subset of channels such that the total cost doesn’t exceed the allocated budget and the total reach is maximized.
In the above discussion, we have come across two words sets and subsets.
What is Set?
Set in mathematics is a well-defined collection of objects that doesn’t vary from person to person.
Example:
- First five Natural Numbers: {1, 2, 3, 4, 5}
- Vowels in English: {a, e, i, o, u}
What is Subset?
A set (B) is said to be the subset of a set (A) if the elements of B are contained in set A.
In other words, if all the elements of set B are contained in set A, then B is said to be the subset of A, and A is said to be the superset of B.
Example: A = {1, 2, 3}, then the subset of A are {}, {1}, {2},{3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.
Must Check: Set and Subset
Note: If a set has n elements, then the number of subsets of the given set is 2N.
Now, let’s move to our topic Subset Sum Problem with the formal definition.
What is Subset Sum Problem?
The subset sum problem is a classical decision problem in computer science. You are given a set of integers and a target sum. The task is to determine if a subset of the given number adds up to the target sum.
Example:
1. A = {5, 7, 3, 9, 1}, Target Sum: 12
Possible subsets of the given set:
{}, {5}, {7}, {3}, {9}, {1}, {5,7}, {5,3}, {5,9}, {5,1}, {7,3}, {7,9}, {7,1}, {3,9}, {3,1}, {9,1}, {5,7,3}, {5,7,9}, {5,7,1}, {5,3,9}, {5,3,1}, {5,9,1}, {7,3,9}, {7,3,1}, {7,9,1}, {3,9,1}, {5, 7, 3, 9}, {5, 7, 3, 1}, {5,3,9,1}, {7, 3, 9, 1}, {5, 7, 3, 9, 1}
Subset that Adds Up: {5, 7} or {3, 9}
Explanation: 5 + 7 = 12 or 3 + 9 = 12
2. B = {2, 4, 6, 8}, Target Sum: 5
Possible subsets of the given set:
{}, {2}, {4}, {6}, {8}, {2,4}, {2,6}, {2,8}, {4,6}, {4,8}, {6,8}, {2,4,6}, {2,4,8}, {2,6,8}, {4,6,8}, {2,4,6,8}
Subset that Adds Up: None
Explanation: No subset of these numbers adds up to 5.
Best-suited C / C++ courses for you
Learn C / C++ with these high-rated online courses
Methods to Solve Subset Sum Problem
Brute Force Approach
- Check all the possibilities of the subset that gives you the target value.
- The above two examples are examples of the Brute Force Approach.
Greedy Algorithm
- Make local optimal choices.
- Example: For {2,3,5}, target sum = 5
- Pick the largest number less than the target, then the next largest, etc.
- Result: We may not always find the best solution.
Backtracking
- Build a solution piece by piece, and backtrack if a piece doesn’t fit.
- Example: For {2,3,5}, target sum = 5
- Start with {2}, then try {3}, backtrack if over {5}
- Result: Finds {5} or {2,3}
Apart from these 3methods, there are two other methods by which we can solve Subset Sum Problem.
- Recursion Method
- Dynamic Method
Subset Sum Problem using Recursion
Recursion is a process in which a method calls itself continuously. Here, we will be using recursion by exploring two possibilities for each element:
- Include the current element in the subset.
- Exclude the current element from the subset.
Algorithm
- Take the input of the array and value ‘sum’.
- Find the size of the array.
- Create a function,
- that return the boolean
- 1: found the subset with the given sum
- 0: subset is not found (no more element is left to explore)
- In the function, check whether the last element of the array is greater than the ‘sum’ or not
- If greater, skip to the next; if not, consider it in the subset.
- that return the boolean
- Keep decreasing the value of the sum by subtracting the value of the last element by keeping the base condition true till the elements are present and till the given sum is not equal to zero.
Now, its time for an example.
Problem Statement: For a given set {3, 34, 4, 12, 5,2} and the target sum = 9. Define a function and use recursive method to check whether there exists a subset with the given sum or not.
#include <stdio.h>
int isSubsetSum(int set[], int n, int sum) { // Base Cases if (sum == 0) return 1; // Found a subset with the given sum if (n == 0) return 0; // No more elements left to explore
// If the last element is greater than the sum, skip it if (set[n-1] > sum) return isSubsetSum(set, n-1, sum);
// Check two possibilities: // 1. Include the last element in the subset // 2. Exclude the last element from the subset return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum - set[n-1]);}
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)) printf("Found a subset with given sum"); else printf("No subset with given sum"); return 0;}
Output
Explanation
In the above program, we have created a recursive function, ‘isSubsetSum‘ that checks, if there exists a subset of ‘set[0,1, 2,…,n-1] with sum equals 0 or not.
The function explores both possibilities for each element, leading to a binary tree of recursive calls. This approach, while simple and elegant, can be inefficient for larger sets due to its exponential time complexity.
Conclusion
In this article we have learned how to solve the subset sum problem in c programming using recursion method and dynamic programming.
Hope you will like the article.
Keep Learning!!
Keep Sharing!!
Read Later
FAQs
What is Subset Sum Problem?
The subset sum problem is a classical decision problem in computer science. You are given au00a0set of integersu00a0and au00a0target sum. The task is to determine if a subset of the given number adds up to the target sum.
What is an example of subset sum problem?
For any given set containing the elements 2, 3, 5 and the target sum equal to 5. Then there exist two subsets containing the elements 2,3 and 5 will satisfy the target sum equals to 5.
What are the different methods to solve the subset sum problem?
We can solve the subset sum problem using Brute Force Approach, Greedy Algorithm, Backtracking, Recursion Method, and Dynamic Method.
Top Picks & New Arrivals
Comments