Table of contents
1.
Introduction
2.
Problem Statement
3.
Aproach1 - Solving Subset Sum Problem using Backtracking
3.1.
Implementation
3.2.
C++
3.3.
Java
3.4.
C#
3.5.
Python
3.6.
JavaScript
3.7.
Complexity Analysis
4.
Approach 2 
4.1.
Implementation
4.2.
C++
4.3.
Java
4.4.
C#
4.5.
Python
4.6.
JavaScript
4.7.
Complexity Analysis
5.
Approach 3
5.1.
Implementation
5.2.
C++
5.3.
Java
5.4.
C#
5.5.
Python
5.6.
JavaScript
5.7.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What optimization did we do on the recursive approach for the Subset Sum problem?
6.2.
What is the difference between the Subset Sum Problem and the Partition Problem?
6.3.
What are the common strategies to solve the Sum of Subset Problem?
6.4.
Can the Sum of Subset Problem be solved using greedy algorithms?
7.
Conclusion
Last Updated: Jan 8, 2025
Medium

Subset Sum Problem

Author NISHANT RANA
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Subset Sum is one of the most popular problems that is asked in interviews. It sounds like it might be a big deal but the problem is actually fairly straightforward and simple. We are provided with an array of integers and a target sum. 

 

We have to determine whether there is a subset of the array present in such a manner that the sum of all the elements in that subset is equal to that of the target value provided. Sounds simple right? Let's get right to the problem then.

(Must Read: Data Structure)

Problem Statement

You are given an array of non-negative integers and an integer value ‘target’. You need to search if there is a subset whose sum is equal to ‘target’.

Let us see a few examples: 

Example 1

Input: 

arr: {1, 2, 3, 4, 5}

target: 10

Output: True

Explanation: 

{1, 4, 5} is one of the subsets of the input array whose subset-sum is equal to the target value i.e., 10.

 

Example 2

Input: 

arr: {3, 7, 12, 2, 5}

target: 11

Output: False

Explanation: 

There is no subset whose subset-sum is equal to the given target value.

Recommended: Try the Problem yourself before moving on to the solution

Aproach1 - Solving Subset Sum Problem using Backtracking

We can use Recursion here to solve this problem.

We can use the pick and non-pick strategy here to search for a subset whose sum is equal to the given target value. We can start from the ‘i’ = 0 index and make two moves, either picking the current element or leaving the current element. 

If you pick the current element, add its value to the sum variable you are maintaining for each recursive call else, don’t add and call the recursive function for the ‘i + 1th’ index. When your ‘i’ reaches the value ‘N’ ( where ‘N’ is the total number of elements in the array), just check if your sum is equal to the target value or not.
 

Refer to the below recursive tree.

recursion tree

 

Do refer to the below implementation of the above approach.

Implementation

  • C++
  • Java
  • C#
  • Python
  • JavaScript

C++

#include <iostream>
using namespace std;

/*
Returns true if there is a subset
of input arr with subset sum equal to given sum
*/
bool isSubsetSum(int arr[], int i, int sum, int target, int n)
{

// Base Cases
if(i == n){
return sum == target;
}
if (sum > target){
return false;
}
if (sum == target){
return true;
}

/* 
Applying the pick and non-pick approach.
We will try both the cases to include or not
include the current element in the subset sum.
*/
return isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n);
}

// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int target = 50;
int n = sizeof(arr) / sizeof(arr[0]);

if (isSubsetSum(arr, 0, 0, target, n) == true){
cout <<"Found a subset with given sum";
}
else{
cout <<"No subset with given sum";
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

public class SubsetSum {

static boolean isSubsetSum(int[] arr, int i, int sum, int target, int n) {
// Base Cases
if (i == n) {
return sum == target;
}
if (sum > target) {
return false;
}
if (sum == target) {
return true;
}

// Pick or non-pick approach
return isSubsetSum(arr, i + 1, sum, target, n) ||
isSubsetSum(arr, i + 1, sum + arr[i], target, n);
}

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int target = 50;
int n = arr.length;

if (isSubsetSum(arr, 0, 0, target, n)) {
System.out.println("Found a subset with given sum");
} else {
System.out.println("No subset with given sum");
}
}
}
You can also try this code with Online Java Compiler
Run Code

C#

using System;

class SubsetSum {

static bool IsSubsetSum(int[] arr, int i, int sum, int target, int n) {
// Base Cases
if (i == n) {
return sum == target;
}
if (sum > target) {
return false;
}
if (sum == target) {
return true;
}

// Pick or non-pick approach
return IsSubsetSum(arr, i + 1, sum, target, n) ||
IsSubsetSum(arr, i + 1, sum + arr[i], target, n);
}

public static void Main() {
int[] arr = {1, 2, 3, 4, 5};
int target = 50;
int n = arr.Length;

if (IsSubsetSum(arr, 0, 0, target, n)) {
Console.WriteLine("Found a subset with given sum");
} else {
Console.WriteLine("No subset with given sum");
}
}
}

Python

def is_subset_sum(arr, i, sum, target, n):
# Base Cases
if i == n:
return sum == target
if sum > target:
return False
if sum == target:
return True

# Pick or non-pick approach
return is_subset_sum(arr, i + 1, sum, target, n) or \
is_subset_sum(arr, i + 1, sum + arr[i], target, n)

# Driver code
arr = [1, 2, 3, 4, 5]
target = 50
n = len(arr)

if is_subset_sum(arr, 0, 0, target, n):
print("Found a subset with given sum")
else:
print("No subset with given sum")
You can also try this code with Online Python Compiler
Run Code

JavaScript

function isSubsetSum(arr, i, sum, target, n) {
// Base Cases
if (i === n) {
return sum === target;
}
if (sum > target) {
return false;
}
if (sum === target) {
return true;
}

// Pick or non-pick approach
return isSubsetSum(arr, i + 1, sum, target, n) ||
isSubsetSum(arr, i + 1, sum + arr[i], target, n);
}

// Driver code
const arr = [1, 2, 3, 4, 5];
const target = 50;
const n = arr.length;

if (isSubsetSum(arr, 0, 0, target, n)) {
console.log("Found a subset with given sum");
} else {
console.log("No subset with given sum");
}
You can also try this code with Online Javascript Compiler
Run Code

 

Output

No subset with given sum

Complexity Analysis

Time Complexity: The time complexity for the approach is 2ⁿ because for each element we are making two decisions either to pick the current element or not to pick the current element.

Space Complexity: The space complexity for the above approach is constant. We are not using any auxiliary space.

Approach 2 

We can optimize APPROACH 1 by memoizing it. We can create a 2D Dynamic Programming table of size (arr.size() + 1) * (target + 1) to store the answer for each ‘i’ and ‘sum’ value because it might be possible that we try to compute the answer for the same ‘i’ and ‘sum’ values.

Refer to the below implementation for the above optimization. (Also see Dynamic Programming Algorithms)

Implementation

  • C++
  • Java
  • C#
  • Python
  • JavaScript

C++

#include <bits/stdc++.h>
using namespace std;

//Making the dp table global
int dp[2000][2000];

/*
Returns true if there is a subset
of input arr with subset sum equal to given sum
*/
int isSubsetSum(int arr[], int i, int sum, int target, int n)
{

// Base Cases
if(i == n){
return sum == target;
}
if (sum > target){
return 0;
}
if (sum == target){
return 1;
}

/*
If the answer for current state
is already present.
*/
if(dp[i][sum] != -1){
return dp[i][sum];
}

/*
Applying the pick and non-pick approach.
We will try both the cases to include or not
include the current element in our subset sum.
*/
return dp[i][sum] = isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n);
}

// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int target = 10;
int n = sizeof(arr) / sizeof(arr[0]);

// Storing the value -1 to the dp table
memset(dp, -1, sizeof(dp));

if (isSubsetSum(arr, 0, 0, target, n)){
cout <<"Found a subset with given sum";
}
else{
cout <<"No subset with given sum";
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Arrays;

public class SubsetSum {

static int[][] dp = new int[2000][2000];

static boolean isSubsetSum(int[] arr, int i, int sum, int target, int n) {
// Base Cases
if (i == n) {
return sum == target;
}
if (sum > target) {
return false;
}
if (sum == target) {
return true;
}

// Check memoized results
if (dp[i][sum] != -1) {
return dp[i][sum] == 1;
}

// Pick or non-pick approach
boolean result = isSubsetSum(arr, i + 1, sum, target, n) ||
isSubsetSum(arr, i + 1, sum + arr[i], target, n);

dp[i][sum] = result ? 1 : 0;
return result;
}

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int target = 10;
int n = arr.length;

// Initialize dp table with -1
for (int[] row : dp) {
Arrays.fill(row, -1);
}

if (isSubsetSum(arr, 0, 0, target, n)) {
System.out.println("Found a subset with given sum");
} else {
System.out.println("No subset with given sum");
}
}
}
You can also try this code with Online Java Compiler
Run Code

C#

using System;

class SubsetSum {

static int[,] dp = new int[2000, 2000];

static bool IsSubsetSum(int[] arr, int i, int sum, int target, int n) {
// Base Cases
if (i == n) {
return sum == target;
}
if (sum > target) {
return false;
}
if (sum == target) {
return true;
}

// Check memoized results
if (dp[i, sum] != -1) {
return dp[i, sum] == 1;
}

// Pick or non-pick approach
bool result = IsSubsetSum(arr, i + 1, sum, target, n) ||
IsSubsetSum(arr, i + 1, sum + arr[i], target, n);

dp[i, sum] = result ? 1 : 0;
return result;
}

public static void Main() {
int[] arr = {1, 2, 3, 4, 5};
int target = 10;
int n = arr.Length;

// Initialize dp table with -1
for (int j = 0; j < dp.GetLength(0); j++)
for (int k = 0; k < dp.GetLength(1); k++)
dp[j, k] = -1;

if (IsSubsetSum(arr, 0, 0, target, n)) {
Console.WriteLine("Found a subset with given sum");
} else {
Console.WriteLine("No subset with given sum");
}
}
}

Python

dp = [[-1 for _ in range(2000)] for _ in range(2000)]

def is_subset_sum(arr, i, sum, target, n):
# Base Cases
if i == n:
return sum == target
if sum > target:
return False
if sum == target:
return True

# Check memoized results
if dp[i][sum] != -1:
return dp[i][sum] == 1

# Pick or non-pick approach
result = is_subset_sum(arr, i + 1, sum, target, n) or \
is_subset_sum(arr, i + 1, sum + arr[i], target, n)

dp[i][sum] = 1 if result else 0
return result

# Driver code
arr = [1, 2, 3, 4, 5]
target = 10
n = len(arr)

if is_subset_sum(arr, 0, 0, target, n):
print("Found a subset with given sum")
else:
print("No subset with given sum")
You can also try this code with Online Python Compiler
Run Code

JavaScript

const dp = Array.from(Array(2000), () => Array(2000).fill(-1));

function isSubsetSum(arr, i, sum, target, n) {
// Base Cases
if (i === n) {
return sum === target;
}
if (sum > target) {
return false;
}
if (sum === target) {
return true;
}

// Check memoized results
if (dp[i][sum] !== -1) {
return dp[i][sum] === 1;
}

// Pick or non-pick approach
const result = isSubsetSum(arr, i + 1, sum, target, n) ||
isSubsetSum(arr, i + 1, sum + arr[i], target, n);

dp[i][sum] = result ? 1 : 0;
return result;
}

// Driver code
const arr = [1, 2, 3, 4, 5];
const target = 10;
const n = arr.length;

if (isSubsetSum(arr, 0, 0, target, n)) {
console.log("Found a subset with given sum");
} else {
console.log("No subset with given sum");
}
You can also try this code with Online Javascript Compiler
Run Code

 

Output

Found a subset with given sum

Complexity Analysis

Time Complexity: The time complexity for the above approach is (arr.size() + 1) * (target + 1) because we are storing the answer for all possible ‘i’ and ‘sum’ pairs, and if we have already calculated the answer for any recursion call we return its answer stores in the DP table.

Space Complexity: The space complexity for the above approach is (arr.size() + 1) * (target + 1) because we are creating a DP table of size (arr.size() + 1) * (target + 1) to store the answer for different ‘i’ and ‘sum’ pairs.

Approach 3

We can solve the above recursive approach in an iterative manner using bottom-up D.P. 

We can create a 2D D.P. similar to the second approach of size (target + 1) * (arr.size() + 1) to store the answer for each ‘i’ and ‘sum’ values.

Implementation

  • C++
  • Java
  • C#
  • Python
  • JavaScript

C++

#include <iostream>
using namespace std;

/*
Returns true if there is a subset of
a[] with sum equal to given sum
*/
bool isSubsetSum(int a[], int n, int sum)
{

/*
The value of dp[i][j] will be
true if there is a subset of
a[0..j-1] with sum equal to i
*/
bool dp[n + 1][sum + 1];

// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
dp[0][i] = true;

/*
If sum is not 0 and set is empty,
then answer is false
*/
for (int i = 1; i <= sum; i++)
dp[i][0] = false;

/*
Fill the dp table in bottom
up manner
*/
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= a[j - 1]){
dp[i][j] = dp[i][j] || dp[i - a[j - 1]][j - 1];
}
}
}

return dp[sum][n];
}

int main()
{
int a[] = { 1, 2, 3, 4, 5 };
int sum = 7;
int n = sizeof(a) / sizeof(a[0]);

if (isSubsetSum(a, n, sum) == true){
cout <<"Found a subset with given sum";
}
else{
cout <<"No subset with given sum";
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

public class SubsetSum {

public static boolean isSubsetSum(int[] a, int n, int sum) {
boolean[][] dp = new boolean[sum + 1][n + 1];

// If sum is 0, the answer is true
for (int i = 0; i <= n; i++) {
dp[0][i] = true;
}

// If sum is not 0 and set is empty, answer is false
for (int i = 1; i <= sum; i++) {
dp[i][0] = false;
}

// Fill dp table in bottom-up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= a[j - 1]) {
dp[i][j] = dp[i][j] || dp[i - a[j - 1]][j - 1];
}
}
}

return dp[sum][n];
}

public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5};
int sum = 7;
int n = a.length;

if (isSubsetSum(a, n, sum)) {
System.out.println("Found a subset with given sum");
} else {
System.out.println("No subset with given sum");
}
}
}
You can also try this code with Online Java Compiler
Run Code

C#

using System;

class SubsetSum {

public static bool IsSubsetSum(int[] a, int n, int sum) {
bool[,] dp = new bool[sum + 1, n + 1];

// If sum is 0, answer is true
for (int i = 0; i <= n; i++) {
dp[0, i] = true;
}

// If sum is not 0 and set is empty, answer is false
for (int i = 1; i <= sum; i++) {
dp[i, 0] = false;
}

// Fill dp table in bottom-up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
dp[i, j] = dp[i, j - 1];
if (i >= a[j - 1]) {
dp[i, j] = dp[i, j] || dp[i - a[j - 1], j - 1];
}
}
}

return dp[sum, n];
}

public static void Main() {
int[] a = {1, 2, 3, 4, 5};
int sum = 7;
int n = a.Length;

if (IsSubsetSum(a, n, sum)) {
Console.WriteLine("Found a subset with given sum");
} else {
Console.WriteLine("No subset with given sum");
}
}
}

Python

def is_subset_sum(a, n, sum):
dp = [[False] * (n + 1) for _ in range(sum + 1)]

# If sum is 0, answer is true
for i in range(n + 1):
dp[0][i] = True

# If sum is not 0 and set is empty, answer is false
for i in range(1, sum + 1):
dp[i][0] = False

# Fill dp table in bottom-up manner
for i in range(1, sum + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i][j - 1]
if i >= a[j - 1]:
dp[i][j] = dp[i][j] or dp[i - a[j - 1]][j - 1]

return dp[sum][n]

# Driver code
a = [1, 2, 3, 4, 5]
sum_value = 7
n = len(a)

if is_subset_sum(a, n, sum_value):
print("Found a subset with given sum")
else:
print("No subset with given sum")
You can also try this code with Online Python Compiler
Run Code

JavaScript

function isSubsetSum(a, n, sum) {
let dp = Array.from({ length: sum + 1 }, () => Array(n + 1).fill(false));

// If sum is 0, answer is true
for (let i = 0; i <= n; i++) {
dp[0][i] = true;
}

// If sum is not 0 and set is empty, answer is false
for (let i = 1; i <= sum; i++) {
dp[i][0] = false;
}

// Fill dp table in bottom-up manner
for (let i = 1; i <= sum; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= a[j - 1]) {
dp[i][j] = dp[i][j] || dp[i - a[j - 1]][j - 1];
}
}
}

return dp[sum][n];
}

// Driver code
let a = [1, 2, 3, 4, 5];
let sum = 7;
let n = a.length;

if (isSubsetSum(a, n, sum)) {
console.log("Found a subset with given sum");
} else {
console.log("No subset with given sum");
}
You can also try this code with Online Javascript Compiler
Run Code

 

OUTPUT

Found a subset with given sum 

Complexity Analysis

Time Complexity: The time complexity for the above approach is (arr.size() + 1) * (target + 1) because we are storing the answer for all possible ‘i’ and ‘sum’ pairs.

Space Complexity: The space complexity for the above approach is (arr.size() + 1) * (target + 1) because we are creating a DP table of size (arr.size() + 1) * (target + 1) to store the answer for different ‘i’ and ‘sum’ pairs.

 

To better understand and implement the code, check out this video for both the recursive and dynamic programming solutions. 

Frequently Asked Questions

What optimization did we do on the recursive approach for the Subset Sum problem?

Since we were computing the answer for the same state at different times, we made a DP table to store the answer for the states we already computed, so that if in the future we need the answer for that state we can directly return the answer from the DP table.

What is the difference between the Subset Sum Problem and the Partition Problem?

The Subset Sum Problem checks if any subset of a set can sum to a target value, while the Partition Problem determines if a set can be divided into two subsets with equal sums. Partition is a special case of subset sum with target as half of the total sum.

What are the common strategies to solve the Sum of Subset Problem?

Common strategies to solve the Subset Sum Problem include dynamic programming (bottom-up and top-down approaches), backtracking for exploring subsets, and memoization to optimize repeated computations.

Can the Sum of Subset Problem be solved using greedy algorithms?

The Subset Sum Problem cannot be solved using greedy algorithms, as they do not guarantee finding an optimal solution for all subsets. Greedy choices may overlook feasible subsets that satisfy the required sum.

Conclusion

In this blog, we explored the popular Subset Sum Problem. We started with the basic brute-force approach using recursion, then advanced to an optimal solution utilizing Dynamic Programming for efficiency. We know your thirst for knowledge is endless, so keep learning and exploring!

Live masterclass