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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!