Solving the Subset Sum Problem using Dynamic Programming in Java

Subset Sum problem in java using Dp

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 :

Given a set of positive integers, and a value sum S, find out if there exists a subset in the array whose sum is equal to given sum S

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 :

A = { 3, 2, 7, 1}, Sum = 6
Output: True 

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

package com.JournalDev;

public class Main {

 public static void main(String[] args) {
        int[] arr = {3,2, 7, 1};
        int sum =6;
        boolean ans = subset_Sum(arr,sum);
        System.out.println(ans);
}
public static boolean subset_Sum(int[] A, int sum)
        {
            int n = A.length;

            boolean[][] M = new boolean[n + 1][sum + 1];

            for (int i = 0; i <= n; i++) {
                M[i][0] = true;
  // sum 0 is true irrespective of the length of the array
            }

            for (int i = 1; i <= n; i++)
            {

                for (int j = 1; j <= sum; j++)
                {
//two options are :
// the current element is a part of the subset.
// the current element is not a part of the subset.

            if (A[i - 1] > j) {
            M[i][j] = M[i - 1][j];
//if the array element is greater than the sum
//take the value from the previous entry
//that is [i-1][j]
                    }
           else {
             M[i][j] = M[i - 1][j] || M[i - 1][j - A[i - 1]];
 // otherwise check the position T[i-1][j - A[i - 1]]
// that is we are trying to get the sum j-A[i-1] from the previous //row.
// if we are able to get a subset that gives the sum of j-A[i-1],
//then we can get a sum of j from ith row as 
//current element is A[I-1].
                    }
                }
            }
            return M[n][sum];
        }
}

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 :

A[i - 1] > j

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.

M[i][j] = M[i - 1][j] || M[i - 1][j - A[i - 1]];

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.

 j - A[i - 1] + (A[i - 1]) = 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages