Given a set of positive integers and an integer s, is there any non-empty subset whose sum to s.

Input:

set = { 7, 3, 2, 5, 8 }

sum = 14

Output: Yes

subset { 7, 2, 5 } sums to 14

Naive algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O(2^{N}N), since there are 2^{N} subsets and, to check each subset, we need to sum at most N elements.

A better exponential time algorithm uses recursion. Subset sum can also be thought of as a special case of the knapsack problem. For each item, there are two possibilities –

2. We exclude current item from subset and recurse for remaining items.

Finally, we return true if we get subset by including or excluding current item else we return false. The base case of the recursion would be when no items are left or sum becomes negative. We return true when sum becomes 0 i.e. subset is found.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using namespace std; // Return true if there exists a subarray of array[0..n] with given sum bool subsetSum(int arr[], int n, int sum) { // return true if sum becomes 0 (subset found) if (sum == 0) return true; // base case: no items left or sum becomes negative if (n < 0 || sum < 0) return false; // Case 1. include current item in the subset (arr[n]) and recurse // for remaining items (n - 1) with remaining sum (sum - arr[n]) bool include = subsetSum(arr, n - 1, sum - arr[n]); // Case 2. exclude current item n from subset and recurse for // remaining items (n - 1) bool exclude = subsetSum(arr, n - 1, sum); // return true if we can get subset by including or excluding the // current item return include || exclude; } int main() { // Input: set of items and a sum int arr[] = { 7, 3, 2, 5, 8 }; int sum = 14; // number of items int n = sizeof(arr) / sizeof(arr[0]); if (subsetSum(arr, n - 1, sum)) cout << "Yes"; else cout << "No"; return 0; } |

**Output: **

Yes

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The problem has an **optimal substructure**. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. Above solution also exhibits **overlapping subproblems**. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by using **Dynamic Programming**, in which subproblem solutions are *Memo*ized rather than computed again and again. Below *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

**Memoized C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <bits/stdc++.h> using namespace std; // create a map to store solutions of subproblems unordered_map<string, int> lookup; // Return true if there exists a subarray of array[0..n] with given sum bool subsetSum(int arr[], int n, int sum) { // return true if sum becomes 0 (subset found) if (sum == 0) return true; // base case: no items left or sum becomes negative if (n < 0 || sum < 0) return false; // construct a unique map key from dynamic elements of the input string key = to_string(n) + "|" + to_string(sum); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // Case 1. include current item in the subset (arr[n]) and recurse // for remaining items (n - 1) with remaining sum (sum - arr[n]) bool include = subsetSum(arr, n - 1, sum - arr[n]); // Case 2. exclude current item n from subset and recurse for // remaining items (n - 1) bool exclude = subsetSum(arr, n - 1, sum); // assign true if we can get subset by including or excluding the // current item lookup[key] = include || exclude; } // return solution to current sub-problem return lookup[key]; } int main() { // Input: set of items and a sum int arr[] = { 7, 3, 2, 5, 8 }; int sum = 14; // number of items int n = sizeof(arr) / sizeof(arr[0]); if (subsetSum(arr, n - 1, sum)) cout << "Yes"; else cout << "No"; return 0; } |

**Output: **

Yes

The time complexity of above solution is O(n x sum). Auxiliary space used by the program is also O(n x sum).

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes T[i][j], for each 1 <= i <= n and 1 <= j <= sum, which is true if subset with sum j can be found using items up to first i items. It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <bits/stdc++.h> using namespace std; // Return true if there exists a subarray of array[0..n) with given sum bool subsetSum(int arr[], int n, int sum) { // T[i][j] stores true if subset with sum j can be attained with // using items up to first i items bool T[n + 1][sum + 1]; // if 0 items in the list and sum is non-zero for (int j = 1; j <= sum; j++) T[0][j] = false; // if sum is zero for (int i = 0; i <= n; i++) T[i][0] = true; // do for ith item for (int i = 1; i <= n; i++) { // consider all sum from 1 to sum for (int j = 1; j <= sum; j++) { // don't include ith element if j-arr[i-1] is negative if (arr[i - 1] > j) T[i][j] = T[i - 1][j]; else // find subset with sum j by excluding or including the ith item T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]]; } } // return maximum value return T[n][sum]; } int main() { // Input: set of items and a sum int arr[] = { 7, 3, 2, 5, 8 }; int sum = 18; // number of items int n = sizeof(arr) / sizeof(arr[0]); if (subsetSum(arr, n, sum)) cout << "Yes"; else cout << "No"; return 0; } |

**Output: **

Yes

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply