### 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)

- if col < array[row-1] then

##### 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