# Subset Sum Problem

## Problem Statement

Given an array of non-negative integers and an integer sum. We have to tell whether there exists any subset in an array whose sum is equal to the given integer sum.

Examples:

Input: arr[] = {3, 34, 4, 12, 3, 2}, sum = 7
Output: True
Explanation: There is a subset (4, 3) with sum 7.

Input: arr[] = {2, 2, 2, 3, 2, 2}, sum = 10
Output: True
Explanation:

## Recursive Approach

For this approach, we have two cases.

• Let’s take the last element and now the sum = target sum – value of ‘last’ element and elements remaining = size of array – 1.
• Now  don’t take the ‘last’ element and now the  sum = target sum and elements remaining = size of array – 1.

Dry Run of the Approach:

Suppose n is the size of the array.

Base Cases

isThereSubsetSum(arr, n, sum) = false, if sum > 0 and n == 0
isThereSubsetSum(arr, n, sum) = true, if sum == 0

### C Implementation Of Recursive Approach

```bool isThereSubsetSum(int arr[], int n, int sum) {
if (sum == 0)
return true;
if (n == 0)
return false;

if (arr[n - 1] > sum)
return isThereSubsetSum(arr, n - 1, sum);

return isThereSubsetSum(arr, n - 1, sum) ||
isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);
}```

### Java Implementation Of Recursive Approach

```static boolean isThereSubsetSum(int arr[],
int n, int sum) {

if (sum == 0)
return true;
if (n == 0)
return false;

if (arr[n - 1] > sum)
return isThereSubsetSum(arr, n - 1, sum);

return isThereSubsetSum(arr, n - 1, sum) ||
isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);
}```

### Python Implementation Of Recursive Approach

```def isThereSubsetSum(arr, n, sum):
if (sum == 0):
return True
if (n == 0):
return False

if (arr[n - 1] > sum):
return isThereSubsetSum(arr, n - 1, sum)

return isThereSubsetSum(
arr, n-1, sum) or isThereSubsetSum(
arr, n-1, sum-arr[n-1])```

Time complexity: The above approach may try all the possible subsets of a given array in the worst case. Therefore the time complexity of the above approach is exponential.

## Dynamic Programming Approach

In this approach, we will make a 2D array of size equal to (size of array + 1) * (target sum + 1) of boolean type. The state dp[i][j] will be true if there is a subset of elements from A[0….i] with a sum value equal to j.

Approach:

• We make a boolean dp[][] and fill it in a top-down manner.
• The value of dp[i][j] will be true if there exists a subset of dp[0..i] with a sum equal to j., otherwise false
• Finally, we return dp[n][sum]

### C Implementation For Subset Sum

```bool isThereSubsetSum(int arr[], int n, int sum) {

bool dp[n + 1][sum + 1];
for (int i = 0; i <= n; i++)
dp[i] = true;

for (int i = 1; i <= sum; i++)
dp[i] = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < arr[i - 1])
dp[i][j] = dp[i - 1][j];
if (j >= arr[i - 1])
dp[i][j] = dp[i - 1][j] ||
dp[i - 1][j - arr[i - 1]];
}
}
return dp[n][sum];
}```

### Java Implementation For Subset Sum

```static boolean isThereSubsetSum(int arr[], int n, int sum) {
boolean dp[][] = new boolean[n + 1][sum + 1];
for (int i = 0; i <= n; i++)
dp[i] = true;

for (int i = 1; i <= sum; i++)
dp[i] = false;

for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
if (j < arr[i - 1])
dp[i][j] = dp[i - 1][j];
if (j >= arr[i - 1])
dp[i][j] = dp[i - 1][j] ||
dp[i - 1][j - arr[i - 1]];
}
}
return dp[n][sum];
}```

### Python Implementation For Subset Sum

```def isThereSubsetSum(arr, n, sum):

dp =([[False for i in range(sum + 1)]
for i in range(n + 1)])

for i in range(n + 1):
dp[i] = True

for i in range(1, sum + 1):
dp[i]= False

for i in range(1, n + 1):
for j in range(1, sum + 1):
if j<arr[i-1]:
dp[i][j] = dp[i-1][j]
if j>= arr[i-1]:
dp[i][j] = (dp[i-1][j] or
dp[i - 1][j-arr[i-1]])

return dp[n][sum]```

Time Complexity: O(N * sum) where N is the size of the array.
Space Complexity: O(N * sum) where N is the size of the array.

## Practice Questions

What subset sum problem gives a suitable example?
The Subset-Sum Problem is to find a subset’ of the given array A = (A1 A2 A3…An) where the elements of the array A are n positive integers in such a way that a’∈A and summation of the elements of that subsets is equal to some positive integer S.

Is the subset sum problem NP-hard?
Yes, it is an NP-hard problem.

Is subset-sum an optimization problem?
Yes, subset-sum is an optimization problem because it has a variety of algorithms for tackling it.

How do you solve subsets?
Subsets can be solved using backtracking and dynamic programming with efficient time complexity.

##### Previous Post ## Find The Missing Number

##### Next Post 