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.

#include<stdio.h>

int main() {
	int arr[] = { 1, 3, 5, 4, 9 };
	int sum = 12;
	int n = sizeof(arr) / sizeof(arr[0]);

	int s;
	int i, j, mat[sum + 1][n + 1];
	for (i = 0; i <= sum + 1; i++)
		for (j = 0; j <= n; j++)
			mat[i][j] = 0;

	//If sum is zero
	for (i = 0; i <= n; i++)
		mat[0][i] = 1;

	//If set is empty
	for (i = 1; i <= sum; i++)
		mat[i][0] = 0;
	//fill the rest of matrix entries
	for (i = 1; i <= sum; i++) {
		for (j = 1; j <= n; j++) {
			mat[i][j] = mat[i][j - 1];
			if (!mat[i][j] && i >= arr[j - 1])
				mat[i][j] = mat[i - arr[j - 1]][j - 1];
		}
	}

	if (mat[sum][n] == 1)
		printf("Yes \n");
	else
		printf("No\n");
	return 0;
}

 



Related Contents to follow