Given a set[] of non-negative integers and a value sum, the task is to print the subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {1,2,1}, sum = 3
Output: [1,2],[2,1]
Explanation: There are subsets [1,2],[2,1] with sum 3.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: []
Explanation: There is no subset that add up to 30.
Subset Sum Problem using Backtracking
Subset sum can also be thought of as a special case of the 0–1 Knapsack problem. For each item, there are two possibilities:
- Include the current element in the subset and recur for the remaining elements with the remaining Sum.
- Exclude the current element from the subset and recur for the remaining elements.
Finally, if Sum becomes 0 then print the elements of current subset. The recursion’s base case would be when no items are left, or the sum becomes negative, then simply return.
Implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Print all subsets if there is atleast one subset of set[]// with sum equal to given sumbool flag = 0;void PrintSubsetSum(int i, int n, int set[], int targetSum, vector<int>& subset){ // targetSum is zero then there exist a // subset. if (targetSum == 0) { // Prints valid subset flag = 1; cout << "[ "; for (int i = 0; i < subset.size(); i++) { cout << subset[i] << " "; } cout << "]"; return; } if (i == n) { // return if we have reached at the end of the array return; } // Not considering current element PrintSubsetSum(i + 1, n, set, targetSum, subset); // consider current element if it is less than or equal // to targetSum if (set[i] <= targetSum) { // push the current element in subset subset.push_back(set[i]); // Recursive call for consider current element PrintSubsetSum(i + 1, n, set, targetSum - set[i], subset); // pop-back element after recursive call to restore // subsets original configuration subset.pop_back(); }}// Driver codeint main(){ // Test case 1 int set[] = { 1, 2, 1 }; int sum = 3; int n = sizeof(set) / sizeof(set[0]); vector<int> subset; cout << "Output 1:" << endl; PrintSubsetSum(0, n, set, sum, subset); cout << endl; flag = 0; // Test case 2 int set2[] = { 3, 34, 4, 12, 5, 2 }; int sum2 = 30; int n2 = sizeof(set) / sizeof(set[0]); vector<int> subset2; cout << "Output 2:" << endl; PrintSubsetSum(0, n2, set2, sum2, subset2); if (!flag) { cout << "There is no such subset"; } return 0;}// This code is contributed by Hem Kishan |
Output 1:
[ 2 1 ][ 1 2 ]
Output 2:
There is no such subset
Complexity analysis:
- Time Complexity: O(2n) The above solution may try all subsets of the given set in the worst case. Therefore time complexity of the above solution is exponential.
- Auxiliary Space: O(n) where n is recursion stack space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
