Subset sum problem using Dynamic Programming | faceprep

Subset sum problem using Dynamic Programming | faceprep

Subset sum problem using Dynamic Programming is discussed here.



Subset sum problem using Dynamic Programming

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

@@coding::1@@




Recommended Programs




Subset sum problem using Dynamic Programming

c