🙏

জয়  শ্রী  রাম

🕉

---

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: