Solving the Subset Sum Problem using Dynamic Programming in Java With Examples

Subset sum problem is a common interview question asked during technical interviews for the position of a software developer.

It is also a very good question to understand the concept of dynamic programming.

Subset Sum Problem Statement

The problem statement is as follows :

An array B is the subset of array A if all the elements of B are present in A. Size of the subset has to be less than or equal to the parent array.

Let’s take an example :

In this case the subarray {3, 2, 1} gives the sum 6. Hence we output true.

Naive Approach to Solve Subset Sum Problem

The naive approach to solve this question would be to go through all the possible subsets.

For n elements there can be 2^n subsets.

As you can guess, that would be computationally very, very, very inefficient.

Dynamic Programming to Solve Subset Sum Problem

To solve the problem using dynamic programming we will be using a table to keep track of sum and current position.

We will create a table that stores boolean values.

The rows of the table indicate the number of elements we are considering. That means at 3rd row, only first three elements are under consideration.

The columns of the table indicate the sum we are trying to make.

The rows go from 0 to length of the array.

The column go from 0 to sum.

Dimension of the table is [length of the array +1, sum+1].

This means that the last cell would have the index as [length of array, sum]. After filling the table, our answer would be in this very cell.

Let’s look at the code :

Java Program for Subset Sum Problem

Output: true

Explanation of the Code

In the first for loop, we set values of the 0th column as true. The 0th column means getting 0 as the sum, which is true irrespective of the elements in consideration.

For row i, the elements under consideration are all the elements from A[0] to A[i-1]. Column j means that the sum we’re trying to make is j.

If the current element is greater than the sum, that is :

We take the value from M[i – 1][j]. The value will be true if without considering the current element (A[i-1]), we are able to achieve the sum j.

In the else case, we look at two positions and do an OR operation.

The position M[i – 1][j] means getting the sum j without adding the current element (A[i-1]).

The position M[i – 1][j – A[i – 1]] means getting the sum j – A[i – 1] in the previous row. If we are able to get the sum j – A[i – 1] from the previous row, then we can add the current element to it and get the sum as j.

Since we are doing an OR operation, if either of the two is true, we can set M[i][j] as true.

In the end we return value of M[n][sum] as the output.

By admin

Leave a Reply