Sum of subset using dynamic programming

Given a set (i.e. an array) of n distinct positive numbers, find a subset whose sum of elements is m.

Algorithm:

• Create for dp table bottom to up approach of size (array.length + 1) X (sum + 1)
• Set true for all value for columns zero (0) because sum zero can be create from any set
• Set false for all value for row one (1) because sum zero can be created by any set except  zero
• Populate dp tale with following configuration
  • if col < array[row-1] then
    • table [row][col] = table [row-1][col] (i.e without taking current element)
  • else
    • table [row]col] = table [row-1][col] || table[row-1] [col – array[row – 1] ] (i.e. without taking current element or with taking current element)

Idiom: With taking or without taking current element

Latest Source Code:
Github: SumOfSubsetUsingDP.java

Output:

Array : [8, 3, 2, 10, 7]
Sum 5 ? true
Sum 12 ? true
Sum 25 ? true
Sum 27 ? true
Sum 50 ? false
Sum 20 ? true