How to solve Subset Sum Problem?

Let's dive in!

It's a problem where you're given an array A = (A1 A2 A3…An) of positive integers, and you need to find a subset of the array such that the sum of the elements in that subset is equal to some positive integers.

Ever heard of Subset-Sum Problem?

Given an array of non-negative integers and an integer sum, can you determine if there exists any subset in the array whose sum is equal to the given integer sum?

Problem Statement

Let's take an example to understand the problem better.

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

This approach is based on two cases-    1. Take last element & calculate sum = target sum - value of last element & elements remaining = size of array - 1.

Recursive Approach

2. Don't take last element & calculate the sum = target sum & elements remaining = size of array - 1.

Time complexity of Recursive Approach  The time complexity of this approach is exponential, but why? Click on the link below to find out the answer.

1. Make a 2D array of size equal to (size of array + 1) * (target sum + 1) of boolean type.   2. 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.

Dynamic Programming Approach

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

Want to explore these approaches and learn how to implement them in various programming languages?

Click on the link below to start your journey.