Explore
Placement Prep

Edit

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