#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);
cout << key << endl;
// 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 decreased 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 get subset by including or excluding 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[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
int sum = 50;
// number of items
int n = sizeof(arr) / sizeof(arr[0]);
if (subsetSum(arr, n - 1, sum))
cout << "Yes";
else
cout << "No";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBjcmVhdGUgYSBtYXAgdG8gc3RvcmUgc29sdXRpb25zIG9mIHN1YnByb2JsZW1zCnVub3JkZXJlZF9tYXA8c3RyaW5nLCBpbnQ+IGxvb2t1cDsKCi8vIFJldHVybiB0cnVlIGlmIHRoZXJlIGV4aXN0cyBhIHN1YmFycmF5IG9mIGFycmF5WzAuLm5dIHdpdGggZ2l2ZW4gc3VtCmJvb2wgc3Vic2V0U3VtKGludCBhcnJbXSwgaW50IG4sIGludCBzdW0pCnsKCS8vIHJldHVybiB0cnVlIGlmIHN1bSBiZWNvbWVzIDAgKHN1YnNldCBmb3VuZCkKCWlmIChzdW0gPT0gMCkKCQlyZXR1cm4gdHJ1ZTsKCgkvLyBiYXNlIGNhc2U6IG5vIGl0ZW1zIGxlZnQgb3Igc3VtIGJlY29tZXMgbmVnYXRpdmUKCWlmIChuIDwgMCB8fCBzdW0gPCAwKQoJCXJldHVybiBmYWxzZTsKCgkvLyBjb25zdHJ1Y3QgYSB1bmlxdWUgbWFwIGtleSBmcm9tIGR5bmFtaWMgZWxlbWVudHMgb2YgdGhlIGlucHV0CglzdHJpbmcga2V5ID0gdG9fc3RyaW5nKG4pICsgInwiICsgdG9fc3RyaW5nKHN1bSk7Cgljb3V0IDw8IGtleSA8PCBlbmRsOwoKCS8vIGlmIHN1Yi1wcm9ibGVtIGlzIHNlZW4gZm9yIHRoZSBmaXJzdCB0aW1lLCBzb2x2ZSBpdCBhbmQgCgkvLyBzdG9yZSBpdHMgcmVzdWx0IGluIGEgbWFwCglpZiAobG9va3VwLmZpbmQoa2V5KSA9PSBsb29rdXAuZW5kKCkpCgl7CgkJLy8gQ2FzZSAxLiBpbmNsdWRlIGN1cnJlbnQgaXRlbSBpbiB0aGUgc3Vic2V0IChhcnJbbl0pIGFuZCByZWN1cnNlCgkJLy8gZm9yIHJlbWFpbmluZyBpdGVtcyAobiAtIDEpIHdpdGggZGVjcmVhc2VkIHN1bSAoc3VtIC0gYXJyW25dKQoJCWJvb2wgaW5jbHVkZSA9IHN1YnNldFN1bShhcnIsIG4gLSAxLCBzdW0gLSBhcnJbbl0pOwoJCQoJCS8vIENhc2UgMi4gZXhjbHVkZSBjdXJyZW50IGl0ZW0gbiBmcm9tIHN1YnNldCBhbmQgcmVjdXJzZSBmb3IgCgkJLy8gcmVtYWluaW5nIGl0ZW1zIChuIC0gMSkKCQlib29sIGV4Y2x1ZGUgPSBzdWJzZXRTdW0oYXJyLCBuIC0gMSwgc3VtKTsKCQkKCQkvLyBhc3NpZ24gdHJ1ZSBpZiB3ZSBnZXQgc3Vic2V0IGJ5IGluY2x1ZGluZyBvciBleGNsdWRpbmcgY3VycmVudCBpdGVtCgkJbG9va3VwW2tleV0gPSBpbmNsdWRlIHx8IGV4Y2x1ZGU7Cgl9CgkKCS8vIHJldHVybiBzb2x1dGlvbiB0byBjdXJyZW50IHN1Yi1wcm9ibGVtCglyZXR1cm4gbG9va3VwW2tleV07Cn0KCmludCBtYWluKCkKewoJLy8gSW5wdXQ6IHNldCBvZiBpdGVtcyBhbmQgYSBzdW0KCWludCBhcnJbXSA9IHsgMSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOSwgMTAsIDExLCAxMiwgMTMsIDE0LCAxNSB9OwoJaW50IHN1bSA9IDUwOwoKCS8vIG51bWJlciBvZiBpdGVtcwoJaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKCWlmIChzdWJzZXRTdW0oYXJyLCBuIC0gMSwgc3VtKSkKCQljb3V0IDw8ICJZZXMiOwoJZWxzZQoJCWNvdXQgPDwgIk5vIjsKCglyZXR1cm4gMDsKfQ==