Given an array arr[] of length N and an integer X, the task is to find the number of subsets with a sum equal to X.
Examples:
Input: arr[] = {1, 2, 3, 3}, X = 6
Output: 3
Explanation: All the possible subsets are {1, 2, 3}, {1, 2, 3} and {3, 3}.Input: arr[] = {1, 1, 1, 1}, X = 1
Output: 4
Space Efficient Approach: This problem has already been discussed in the article here. This article focuses on a similar Dynamic Programming approach which uses only O(X) space. The standard DP relation of solving this problem as discussed in the above article is:
dp[i][C] = dp[i – 1][C – arr[i]] + dp[i – 1][C]
where dp[i][C] stores the number of subsets of the subarray arr[0… i] such that their sum is equal to C. It can be noted that the dp[i]th state only requires the array values of the dp[i – 1]th state. Hence the above relation can be simplified into the following:
dp[C] = dp[C – arr[i]] + dp[C]
Here, a good point to note is that during the calculation of dp[C], the variable C must be iterated in decreasing order in order to avoid the duplicity of arr[i] in the subset-sum count.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of subsets// having the given sumint subsetSum(int arr[], int n, int sum){ // Initializing the dp-table int dp[sum + 1] = {}; // Case for sum of elements in empty set dp[0] = 1; // Loop to iterate over array elements for (int i = 0; i < n; i++) { for (int j = sum; j >= 0; j--) { // If j-arr[i] is a valid index if (j - arr[i] >= 0) { dp[j] = dp[j - arr[i]] + dp[j]; } } } // Return answer return dp[sum];}// Driven Codeint main(){ int arr[] = { 1, 1, 1, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int sum = 1; cout << subsetSum(arr, N, sum) << endl; return 0;} |
Java
// Java implementation of the above approachimport java.util.*;public class GFG{ // Function to find the count of subsets// having the given sumstatic int subsetSum(int arr[], int n, int sum){ // Initializing the dp-table int dp[] = new int[sum + 1]; // Case for sum of elements in empty set dp[0] = 1; // Loop to iterate over array elements for (int i = 0; i < n; i++) { for (int j = sum; j >= 0; j--) { // If j-arr[i] is a valid index if (j - arr[i] >= 0) { dp[j] = dp[j - arr[i]] + dp[j]; } } } // Return answer return dp[sum];}// Driver codepublic static void main(String args[]){ int arr[] = { 1, 1, 1, 1 }; int N = arr.length; int sum = 1; System.out.println(subsetSum(arr, N, sum));}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python implementation of the above approach# Function to find the count of subsets# having the given sumdef subsetSum(arr, n, sum): # Initializing the dp-table dp = [0] * (sum + 1) # Case for sum of elements in empty set dp[0] = 1; # Loop to iterate over array elements for i in range(n): for j in range(sum, 0, -1): # If j-arr[i] is a valid index if (j - arr[i] >= 0): dp[j] = dp[j - arr[i]] + dp[j]; # Return answer return dp[sum];# Driven Codearr = [1, 1, 1, 1];N = len(arr)sum = 1;print(subsetSum(arr, N, sum))# This code is contributed by gfgking. |
C#
// C# implementation of the above approachusing System;public class GFG{ // Function to find the count of subsets// having the given sumstatic int subsetSum(int []arr, int n, int sum){ // Initializing the dp-table int []dp = new int[sum + 1]; // Case for sum of elements in empty set dp[0] = 1; // Loop to iterate over array elements for (int i = 0; i < n; i++) { for (int j = sum; j >= 0; j--) { // If j-arr[i] is a valid index if (j - arr[i] >= 0) { dp[j] = dp[j - arr[i]] + dp[j]; } } } // Return answer return dp[sum];}// Driver codepublic static void Main(String []args){ int []arr = { 1, 1, 1, 1 }; int N = arr.Length; int sum = 1; Console.WriteLine(subsetSum(arr, N, sum));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation of the above approach// Function to find the count of subsets// having the given sumfunction subsetSum(arr, n, sum) { // Initializing the dp-table let dp = new Array(sum + 1).fill(0) // Case for sum of elements in empty set dp[0] = 1; // Loop to iterate over array elements for (let i = 0; i < n; i++) { for (let j = sum; j >= 0; j--) { // If j-arr[i] is a valid index if (j - arr[i] >= 0) { dp[j] = dp[j - arr[i]] + dp[j]; } } } // Return answer return dp[sum];}// Driven Codelet arr = [1, 1, 1, 1];let N = arr.length;let sum = 1;document.write(subsetSum(arr, N, sum))// This code is contributed by gfgking.</script> |
Output
4
Time Complexity: O(N * X)
Auxiliary Space: O(X)
Another Approach (Memoised dynamic programming):
The problem can be solved using memoised dynamic programming. We can create a 2D dp array where dp[i][j] represents the number of subsets of arr[0…i] with sum equal to j. The recursive relation for dp[i][j] can be defined as follows:
- If i = 0, dp[0][j] = 1 if arr[0] == j else 0
- If i > 0, dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]], if j >= arr[i]
- If i > 0, dp[i][j] = dp[i-1][j], if j < arr[i]
The base case for i = 0 can be easily computed as the subset containing only the first element of the array has a sum equal to arr[0] and no other sum. For all other i > 0, we need to consider two cases: either the ith element is included in a subset with sum j, or it is not included. If it is not included, we need to find the number of subsets of arr[0…(i-1)] with sum equal to j. If it is included, we need to find the number of subsets of arr[0…(i-1)] with sum equal to (j – arr[i]).
The final answer will be stored in dp[N-1][X], as we need to find the number of subsets of arr[0…N-1] with sum equal to X.
Algorithm:
- Define a recursive function countSubsets(arr, X, dp, i, sum) that takes the following parameters:
- arr: The input array
- X: The target sum
- dp: The memoization table
- i: The index of the current element being considered
- sum: The current sum of elements in the subset
- If i is less than 0, return 1 if sum is equal to X, otherwise return 0
- If dp[i][sum] is not equal to -1, return dp[i][sum]
- Initialize ans to countSubsets(arr, X, dp, i – 1, sum)
- If sum plus the ith element of arr is less than or equal to X, add countSubsets(arr, X, dp, i – 1, sum + arr[i]) to ans
- Set dp[i][sum] to ans
- Return ans
- Initialize the DP table dp to all -1 values
- Call countSubsets(arr, X, dp, arr.size() – 1, 0) and store the result in ans
- Print ans as the number of subsets with a sum equal to X in arr
Below is the implementation of the approach:
C++
#include <bits/stdc++.h>using namespace std;// Recursive function to count subsets with a sum equal to Xint countSubsets(vector<int>& arr, int X, vector<vector<int>> &dp, int i, int sum) { // Base case: if we have reached the end of the array if (i < 0) { // If the sum is equal to X, return 1, else return 0 return (sum == X ? 1 : 0); } // If the subproblem has already been solved, return the solution if (dp[i][sum] != -1) { return dp[i][sum]; } // If we don't include the current element in the subset int ans = countSubsets(arr, X, dp, i - 1, sum); // If we include the current element in the subset if (sum + arr[i] <= X) { ans += countSubsets(arr, X, dp, i - 1, sum + arr[i]); } // Memoize the solution to the subproblem dp[i][sum] = ans; // Return the solution to the current subproblem return ans;}int main() { // Example usage vector<int> arr = { 1, 1, 1, 1 }; int X = 1; // Initialize the DP table with -1 vector<vector<int>> dp(arr.size()+1, vector<int>(X+1, -1)); // Count the number of subsets with a sum equal to X int ans = countSubsets(arr, X, dp, arr.size() - 1, 0); // Print the result cout << ans << endl; return 0;} |
Java
// Java implementationimport java.util.*;public class Main { // Recursive function to count subsets with a sum equal to X public static int countSubsets(List<Integer> arr, int X, int[][] dp, int i, int sum) { // Base case: if we have reached the end of the array if (i < 0) { // If the sum is equal to X, return 1, else return 0 return (sum == X ? 1 : 0); } // If the subproblem has already been solved, return the solution if (dp[i][sum] != -1) { return dp[i][sum]; } // If we don't include the current element in the subset int ans = countSubsets(arr, X, dp, i - 1, sum); // If we include the current element in the subset if (sum + arr.get(i) <= X) { ans += countSubsets(arr, X, dp, i - 1, sum + arr.get(i)); } // Memoize the solution to the subproblem dp[i][sum] = ans; // Return the solution to the current subproblem return ans; } public static void main(String[] args) { // Example usage List<Integer> arr = Arrays.asList(1, 1, 1, 1); int X = 1; // Initialize the DP table with -1 int[][] dp = new int[arr.size() + 1][X + 1]; for (int i = 0; i <= arr.size(); i++) { Arrays.fill(dp[i], -1); } // Count the number of subsets with a sum equal to X int ans = countSubsets(arr, X, dp, arr.size() - 1, 0); // Print the result System.out.println(ans); }}// This code is contributed by Sakshi |
Python3
# Recursive function to count subsets with a sum equal to Xdef count_subsets(arr, X, dp, i, sum): # Base case: if we have reached the end of the array if i < 0: # If the sum is equal to X, return 1, else return 0 return 1 if sum == X else 0 # If the subproblem has already been solved, return the solution if dp[i][sum] != -1: return dp[i][sum] # If we don't include the current element in the subset ans = count_subsets(arr, X, dp, i - 1, sum) # If we include the current element in the subset if sum + arr[i] <= X: ans += count_subsets(arr, X, dp, i - 1, sum + arr[i]) # Memoize the solution to the subproblem dp[i][sum] = ans # Return the solution to the current subproblem return ansif __name__ == "__main__": # Example usage arr = [1, 1, 1, 1] X = 1 # Initialize the DP table with -1 dp = [[-1 for _ in range(X + 1)] for _ in range(len(arr) + 1)] # Count the number of subsets with a sum equal to X ans = count_subsets(arr, X, dp, len(arr) - 1, 0) # Print the result print(ans) |
C#
using System;using System.Collections.Generic;class Program{ // Recursive function to count subsets with a sum equal to X static int CountSubsets(List<int> arr, int X, int[,] dp, int i, int sum) { // Base case: if we have reached the end of the array if (i < 0) { // If the sum is equal to X, return 1, else return 0 return (sum == X ? 1 : 0); } // If the subproblem has already been solved, return the solution if (dp[i, sum] != -1) { return dp[i, sum]; } // If we don't include the current element in the subset int ans = CountSubsets(arr, X, dp, i - 1, sum); // If we include the current element in the subset if (sum + arr[i] <= X) { ans += CountSubsets(arr, X, dp, i - 1, sum + arr[i]); } // Memoize the solution to the subproblem dp[i, sum] = ans; // Return the solution to the current subproblem return ans; } static void Main(string[] args) { // Example usage List<int> arr = new List<int> { 1, 1, 1, 1 }; int X = 1; // Initialize the DP table with -1 int[,] dp = new int[arr.Count + 1, X + 1]; for (int i = 0; i <= arr.Count; i++) { for (int j = 0; j <= X; j++) { dp[i, j] = -1; } } // Count the number of subsets with a sum equal to X int ans = CountSubsets(arr, X, dp, arr.Count - 1, 0); // Print the result Console.WriteLine(ans); }} |
Javascript
// Recursive function to count subsets with a sum equal to Xconst countSubsets = (arr, X, dp, i, sum) => { // Base case: if we have reached the end of the array if (i < 0) { return (sum === X ? 1 : 0); } // If the subproblem has already been solved, return the solution if (dp[i][sum] !== -1) { return dp[i][sum]; } // If we don't include the current element in the subset let ans = countSubsets(arr, X, dp, i - 1, sum); // If we include the current element in the subset if (sum + arr[i] <= X) { ans += countSubsets(arr, X, dp, i - 1, sum + arr[i]); } // Memoize the solution to the subproblem dp[i][sum] = ans; // Return the solution to the current subproblem return ans;};// Driver codeconst arr = [1, 1, 1, 1];const X = 1;const dp = new Array(arr.length + 1).fill().map(() => new Array(X + 1).fill(-1));const ans = countSubsets(arr, X, dp, arr.length - 1, 0);console.log(ans); |
Output
4
Time Complexity: O(N * X), where N is the size of the array and X is the target sum. This is because each subproblem is solved only once, and there are N * X possible subproblems.
Auxiliary Space: O(N * X), as we are using a 2D array of size (N + 1) * (X + 1) to store the solutions to the subproblems.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
