Subset Sum Problem (Recursion & Dynamic Programming)

Given an integer array "arr" of size "n" and an integer "sum", the task is to find whether there exists a subset in "arr" whose sum equals "sum".

If such a subset exists, return "true," otherwise return "false."

Input: arr[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: true
Possible subsets are: {3, 4, 2}, {4,5}

Input: arr[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: false

Solutions

Method 1: Memoization

The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.

We can see that in each recursive call only the value of "n" and "sum" changes, so we can store and reuse the result of a function(..n, sum..) call using a "n * sum" 2-D array.

The 2-D array will store a particular state (n, sum) if we get it the first time.

Now, if we come across the same state (n, w) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.


	package com.cb.dp;

	/*
	* DP-Memoization
	* Time Complexity: sum*n
	* Space: sum*n + O(n) auxiliary stack space
	* */
	public class Dp2_SubsetSumProblem {
	public static boolean isSubsetSum(int[] arr, int sum, int n, int table[][]) {

	// base case
	if (sum == 0)
	return true;
	if (n == 0)
	return false;

	// check if already calculated
	if (table[sum][n] != -1)
	return table[sum][n] == 1 ? true : false;

	// if current element is greater than remaining sum
	if (arr[n - 1] > sum) {
	boolean flag = isSubsetSum(arr, sum, n - 1, table);
	// store in table before return
	table[sum][n] = flag ? 1 : 0;
	return flag;
	}

	// check if sum exists, when including or excluding current element
	boolean flag = isSubsetSum(arr, sum - arr[n - 1], n - 1, table) \|\| isSubsetSum(arr, sum, n - 1, table);
	// store in table before return
	table[sum][n] = flag ? 1 : 0;
	return flag;
	}

	public static void main(String[] args) {
	int[] set = {3, 34, 4, 12, 5, 2};
	int sum = 9;
	int n = set.length;

	int table[][] = new int[sum + 1][n + 1];
	for (int i = 0; i < table.length; i++) {
	for (int j = 0; j < table[i].length; j++)
	table[i][j] = -1;
	}

	System.out.println(isSubsetSum(set, sum, n, table)); // true

	}
	}

view raw Dp2_SubsetSumProblem.java hosted with ❤ by GitHub

Complexity

The time complexity of this solution is (n * sum).

In addition, O(n * w) auxiliary space was used by the table and O(n) by call stack.

Method 2: Recursion

The idea of the recursive approach is to consider all subsets of items and find whether there exists a subset whose sum equals "sum".

While considering an item, we have one of the following two choices:

Choice 1: The item is included in the optimal subsetâ€”decrease the sum by the item value.
Choice 2: The item is not included in the optimal setâ€”don't do anything.

While picking an element, also make sure that the value of the item is less than or equal to the remaining "sum".

If sum is exhausted (equals to "0"), then return "true" and if array is exhausted (n equals to "0"), return "false".

	package com.cb.recursion;

	/*
	* Recursion
	* Subset Sum
	* Time Complexity: 2^n
	* */
	public class R19_SubsetSumProblem {
	public static boolean isSubsetSum(int[] arr, int sum, int n) {

	// base case
	if (sum == 0)
	return true;
	if (n == 0)
	return false;

	// if current element is greater than remaining sum
	if (arr[n - 1] > sum)
	return isSubsetSum(arr, sum, n - 1);

	// check if sum exists, when including or excluding current element
	return isSubsetSum(arr, sum - arr[n - 1], n - 1) \|\| isSubsetSum(arr, sum, n - 1);
	}

	public static void main(String[] args) {
	int[] set = {3, 34, 4, 12, 5, 2};
	int sum = 9;
	int n = set.length;
	System.out.println(isSubsetSum(set, sum, n)); // true

	int[] set1 = {3, 34, 4, 12, 5, 2};
	int sum1 = 30;
	int n1 = set.length;
	System.out.println(isSubsetSum(set1, sum1, n1)); // false
	}
	}