Count Subset Sum
Application of 0/1 Knapsack Concept

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Space Optimization:
I highly recommend looking at the Space Optimization in 0/1 Knapsack Problem first before looking at the code below:
Java code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn