Let us learn Subset Sum Problem Dynamic Programming.The Subset Sum problem takes as input a set X = {x1, x2 ,…, xn} of n integers and another integer K. The problem is to check if there exists a subset X’ of X whose elements sum to K and finds the subset if there’s any. For example, if X = {1 3 5 4 9} and K = 12 then the answer is YES since the subset X’ = {3,5,4} has a sum of 12. 

Dynamic programming solution is an optimized solution for subset sum problem with complexity O(sum*length of set).

Explanation:
set[1 3 5 4 9]
N=5 sum=12

1) Make a matrix of size (sum+1)(N+1) and initialize each matrix entries false(0).
mat[sum +1][N+1]

0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0  0    0   0   0   0

2) Elemets of matrix would be either 1(true) or 0(false);

3) mat[i][j] = true(1); indicates that there is a subset of set[0..j-1] which contains the sum i.

4) matrix[0][j] = true(1); where 1 <= j <= N because in any set there will be empty subset with sum 0;

1   1   1   1    1  1
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0

5) matrix[i][0] = false(0); where 1 <= i <= sum becuase we can’t find a sum > 0 in an empty set.

1   1   1   1    1  1
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
0   0   0   0    0   0
6) Rest of matrix entries will be as below.

matrix[i][j] = matrix[i][j-1];

If there exists a subset of set[0..j-2] with the sum i; then there exits a subset of set[0..j-1] also with the sum i.
If i >= set[j-1]; we check to see if mat[i – set[j-1]][j-1] is true. This means check if there is any subset of set[0..j-2] with sum i-set[j-1].
If there is, then we assign true to this entry.

The step 6 would make mat[sum +1][n+1] as follows:

                    arr —————0    1     3     5     4   9
sum

0                                           1    1    1    1     1     1
1                                           0    1    1    1     1     1
2                                           0    0     0    0     0    0
3                                           0    0     1    1     1    1
4                                           0    0     1    1     1    1
5                                           0    0     0    1     1    1
6                                           0    0     0    1     1    1
7                                           0    0     0    0     1    1
8                                           0    0     0    1     1    1
9                                           0    0     0    1     1    1
10                                         0    0     0    0     1    1
11                                         0    0     0    0     0    0
12                                         0    0     0    0     1    1

6) Let target sum is 12 then check mat[12][N], where N is 5 in our example, if mat[12][N] is true ,answer is YES.