Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Subset sum problem using Dynamic Programming | FACE Prep

Published on 11 Mar 2020

Subset sum problem using Dynamic Programming is discussed here. Given an array and a value, find if there is a subset of the given set with the sum equal to the given sum.


For example,


Sample Input:


10 (Number of elements of the array)


100 (Sum value)


18 23 17 29 1 6 7 30 7 6 (Array elements)


Sample Output:


Yes


Explanation:


18 + 23 + 17 + 29 + 6 + 7 = 100


Algorithm for subset sum problem


  • Create a boolean 2D array table[][] and fill it in a bottom-up manner.
  • The value of table[i][j] will be true if there is a subset of the set[0..j-1] with the given sum equal to i., otherwise false.
  • Finally, we return table[sum][n]


Program for the subset sum problem using dynamic programming


C++

Output
Input - 5 15
2 3 4 5 1
Output -
Yes


Test Case 1

I/P

5 15

2 3 4 5 1

O/P

Yes


Test Case 2

I/P

10 20

18 23 17 29 1 6 7 30 7 6

O/P

Yes


Test Case 3

I/P

10 100

18 23 17 29 1 6 7 30 7 6

O/P

Yes


Test Case 4

I/P

10 28

18 23 17 29 1 6 7 30 7 6

O/P

No


Test Case 5

I/P

10 78

18 23 17 29 1 6 7 30 7 6

O/P

Yes


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises