• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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 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:


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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:


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Space Optimization:


I highly recommend looking at the Space Optimization in 0/1 Knapsack Problem first before looking at the code below:


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave