Count Subset Sum
Application of 0/1 Knapsack Concept

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
Given an array arr[] of length N and an integer X, the task is to find the number of subsets with sum equal to X.
Examples:
Input: arr[] = {1, 2, 3, 3}, X = 6
Output: 3
All the possible subsets are {1, 2, 3}, {1, 2, 3} and {3, 3}
Input: arr[] = {1, 1, 1, 1}, X = 1
Output: 4
Solution:
Please have a strong understanding of the Subset Sum Problem before going through the solution for this problem.
Basically this problem is same as Subset Sum Problem with the only difference that instead of returning whether there exists at least one subset with desired sum, here in this problem we compute count of all such subsets.
We wil start with the code of Subset Sum Problem and will show you how to transform the same code to achieve our end goal for this problem.
Let's take a look at the implementation of Subset Sum Problem discussed in Partition Equal Subset Sum chapter:
Java code:
Login to Access Content
Python code:
Login to Access Content
The below code shows how we transform the above code to compute count of subset sum. I have put all the transformation logic in the inline comment:
Java code:
Login to Access Content
Python code:
Login to Access Content
Space Optimization:
I highly recommend looking at the Space Optimization in 0/1 Knapsack Problem first before looking at the code below:
Java code:
Login to Access Content
Python code:
Login to Access Content
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.