Given an array ‘arr’ consisting of integers, the task is to find the number of subsets such that their sum is equal to zero. An empty subset should also be considered.
Examples:
Input : arr[] = {2, 2, -4}
Output : 2
All possible subsets:
{} = 0
{2} = 2
{2} = 2
{-4} = -4
{2, 2} = 4
{2, -4} = -2
{2, -4} = -4
{2, 2, -4} = 0
Since, {} and {2, 2, -4} are only possible subsets
with sum 0, ans will be 2.
Input : arr[] = {1, 1, 1, 1}
Output : 1
{} is the only possible subset with
sum 0, thus ans equals 1.
One simple approach is to generate all possible subsets recursively and count the number of subsets with a sum equals to 0. The time complexity of this approach will be O(2^n).
A better approach will be using Dynamic programming.
Let’s suppose the sum of all the elements we have selected up to index ‘i-1’ is ‘S’. So, starting from index ‘i’, we have to find the number of subsets of the sub-array{i, N-1} with sum equals -S.
Let’s define dp[i][S]. It means the number of the subset of the subarray{i, N-1} of ‘arr’ with sum equals ‘-S’.
If we are at ith index, we have two choices, i.e. to include it in the sum or leave it.
Thus, the required recurrence relation becomes
dp[i][s] = dp[i+1][s+arr[i]] + dp[i+1][s]
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>#define maxSum 100#define arrSize 51using namespace std;// variable to store// states of dpint dp[arrSize][maxSum];bool visit[arrSize][maxSum];// To find the number of subsets with sum equal to 0// Since S can be negative, we will maxSum// to it to make it positiveint SubsetCnt(int i, int s, int arr[], int n){ // Base cases if (i == n) { if (s == 0) return 1; else return 0; } // Returns the value if a state is already solved if (visit[i][s + maxSum]) return dp[i][s + maxSum]; // If the state is not visited, then continue visit[i][s + maxSum] = 1; // Recurrence relation dp[i][s + maxSum] = SubsetCnt(i + 1, s + arr[i], arr, n) + SubsetCnt(i + 1, s, arr, n); // Returning the value return dp[i][s + maxSum];}// Driver functionint main(){ int arr[] = { 2, 2, 2, -4, -4 }; int n = sizeof(arr) / sizeof(int); cout << SubsetCnt(0, 0, arr, n);} |
Java
// Java implementation of above approachclass GFG { static int maxSum = 100; static int arrSize = 51; // variable to store // states of dp static int[][] dp = new int[arrSize][maxSum]; static boolean[][] visit = new boolean[arrSize][maxSum]; // To find the number of subsets with sum equal to 0 // Since S can be negative, we will maxSum // to it to make it positive static int SubsetCnt(int i, int s, int arr[], int n) { // Base cases if (i == n) { if (s == 0) { return 1; } else { return 0; } } // Returns the value if a state is already solved if (visit[i][s + arrSize]) { return dp[i][s + arrSize]; } // If the state is not visited, then continue visit[i][s + arrSize] = true; // Recurrence relation dp[i][s + arrSize] = SubsetCnt(i + 1, s + arr[i], arr, n) + SubsetCnt(i + 1, s, arr, n); // Returning the value return dp[i][s + arrSize]; } // Driver function public static void main(String[] args) { int arr[] = {2, 2, 2, -4, -4}; int n = arr.length; System.out.println(SubsetCnt(0, 0, arr, n)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of above approach import numpy as npmaxSum = 100arrSize = 51# variable to store # states of dp dp = np.zeros((arrSize, maxSum)); visit = np.zeros((arrSize, maxSum)); # To find the number of subsets # with sum equal to 0.# Since S can be negative, # we will maxSum to it# to make it positive def SubsetCnt(i, s, arr, n) : # Base cases if (i == n) : if (s == 0) : return 1; else : return 0; # Returns the value # if a state is already solved if (visit[i][s + arrSize]) : return dp[i][s + arrSize]; # If the state is not visited, # then continue visit[i][s + arrSize] = 1; # Recurrence relation dp[i][s + arrSize ] = (SubsetCnt(i + 1, s + arr[i], arr, n) + SubsetCnt(i + 1, s, arr, n)); # Returning the value return dp[i][s + arrSize]; # Driver Codeif __name__ == "__main__" : arr = [ 2, 2, 2, -4, -4 ]; n = len(arr); print(SubsetCnt(0, 0, arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approachusing System;class GFG { static int maxSum = 100; static int arrSize = 51; // variable to store // states of dp static int [,]dp = new int[arrSize, maxSum]; static bool [,]visit = new bool[arrSize, maxSum]; // To find the number of subsets with sum equal to 0 // Since S can be negative, we will maxSum // to it to make it positive static int SubsetCnt(int i, int s, int []arr, int n) { // Base cases if (i == n) { if (s == 0) { return 1; } else { return 0; } } // Returns the value if a state is already solved if (visit[i, s + arrSize]) { return dp[i, s + arrSize]; } // If the state is not visited, then continue visit[i, s + arrSize] = true; // Recurrence relation dp[i, s + arrSize] = SubsetCnt(i + 1, s + arr[i], arr, n) + SubsetCnt(i + 1, s, arr, n); // Returning the value return dp[i,s + arrSize]; } // Driver code public static void Main() { int []arr = {2, 2, 2, -4, -4}; int n = arr.Length; Console.WriteLine(SubsetCnt(0, 0, arr, n)); }}// This code contributed by anuj_67.. |
Javascript
<script>var maxSum = 100var arrSize = 51// variable to store// states of dpvar dp = Array.from(Array(arrSize), ()=> Array(maxSum));var visit = Array.from(Array(arrSize), ()=> Array(maxSum));// To find the number of subsets with sum equal to 0// Since S can be negative, we will maxSum// to it to make it positivefunction SubsetCnt(i, s, arr, n){ // Base cases if (i == n) { if (s == 0) return 1; else return 0; } // Returns the value if a state is already solved if (visit[i][s + maxSum]) return dp[i][s + maxSum]; // If the state is not visited, then continue visit[i][s + maxSum] = 1; // Recurrence relation dp[i][s + maxSum] = SubsetCnt(i + 1, s + arr[i], arr, n) + SubsetCnt(i + 1, s, arr, n); // Returning the value return dp[i][s + maxSum];}// Driver functionvar arr = [2, 2, 2, -4, -4];var n = arr.length;document.write( SubsetCnt(0, 0, arr, n));</script> |
Output
7
Time Complexity: O(N*S), where N is the number of elements in the array, and S is the sum of all the elements.
Auxiliary Space: O(N*S)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems.
- Initialize the DP with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in return dp[n][maxSum].
Implementation :
C++
#include <bits/stdc++.h>#define maxSum 100#define arrSize 51using namespace std;// To find the number of subsets with sum equal to 0// Since S can be negative, we will maxSum// to it to make it positiveint SubsetCnt(int arr[], int n){ int dp[n + 1][maxSum * 2 + 1]; // Initializing first column with 1 for (int i = 0; i <= n; i++) { dp[i][maxSum] = 1; } // Initializing rest of the matrix with 0 for (int i = 1; i <= maxSum * 2; i++) { dp[0][i] = 0; } // Filling up the dp matrix for (int i = 1; i <= n; i++) { for (int j = -maxSum; j <= maxSum; j++) { int val = arr[i - 1]; if (j - val + maxSum >= 0 && j - val + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j - val + maxSum]; } if (j + maxSum >= 0 && j + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j + maxSum]; } } } // return final answer return dp[n][maxSum];}// Driver codeint main(){ int arr[] = { 2, 2, 2, -4, -4 }; int n = sizeof(arr) / sizeof(int); // function call cout << SubsetCnt(arr, n);} |
Java
import java.util.*;public class Main { static int maxSum = 100; static int arrSize = 51; // To find the number of subsets with sum equal to 0 // Since S can be negative, we will maxSum // to it to make it positive static int SubsetCnt(int arr[], int n) { int dp[][] = new int[n + 1][maxSum * 2 + 1]; // Initializing first column with 1 for (int i = 0; i <= n; i++) { dp[i][maxSum] = 1; } // Initializing rest of the matrix with 0 for (int i = 1; i <= maxSum * 2; i++) { dp[0][i] = 0; } // Filling up the dp matrix for (int i = 1; i <= n; i++) { for (int j = -maxSum; j <= maxSum; j++) { int val = arr[i - 1]; if (j - val + maxSum >= 0 && j - val + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j - val + maxSum]; } if (j + maxSum >= 0 && j + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j + maxSum]; } } } // return final answer return dp[n][maxSum]; } // Driver code public static void main(String[] args) { int arr[] = { 2, 2, 2, -4, -4 }; int n = arr.length; // function call System.out.println(SubsetCnt(arr, n)); }} |
Python
# Python implementation of the approachMAX_SUM = 100ARR_SIZE = 51# To find the number of subsets with sum equal to 0# Since S can be negative, we will add MAX_SUM# to it to make it positivedef SubsetCnt(arr, n): dp = [[0 for i in range(MAX_SUM*2+1)] for j in range(n+1)] # Initializing first column with 1 for i in range(n+1): dp[i][MAX_SUM] = 1 # Initializing rest of the matrix with 0 for i in range(1, MAX_SUM*2+1): dp[0][i] = 0 # Filling up the dp matrix for i in range(1, n+1): for j in range(-MAX_SUM, MAX_SUM+1): val = arr[i-1] if j-val+MAX_SUM >= 0 and j-val+MAX_SUM <= MAX_SUM*2: dp[i][j+MAX_SUM] += dp[i-1][j-val+MAX_SUM] if j+MAX_SUM >= 0 and j+MAX_SUM <= MAX_SUM*2: dp[i][j+MAX_SUM] += dp[i-1][j+MAX_SUM] # return final answer return dp[n][MAX_SUM]# Driver codeif __name__ == '__main__': arr = [2, 2, 2, -4, -4] n = len(arr) # function call print(SubsetCnt(arr, n)) |
C#
using System;class Program{ // Function to find the number of subsets with a sum equal to 0 static int SubsetCnt(int[] arr, int n) { int maxSum = 100; // Maximum possible sum int[][] dp = new int[n + 1][]; // Create a 2D array 'dp' to store intermediate results for (int i = 0; i <= n; i++) { dp[i] = new int[maxSum * 2 + 1]; } // Initializing the first column with 1, representing an empty subset for (int i = 0; i <= n; i++) { dp[i][maxSum] = 1; } // Initializing the rest of the matrix with 0 for (int i = 1; i <= maxSum * 2; i++) { dp[0][i] = 0; } // Filling up the dp matrix for (int i = 1; i <= n; i++) { for (int j = -maxSum; j <= maxSum; j++) { int val = arr[i - 1]; if (j - val + maxSum >= 0 && j - val + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j - val + maxSum]; } if (j + maxSum >= 0 && j + maxSum <= maxSum * 2) { dp[i][j + maxSum] += dp[i - 1][j + maxSum]; } } } // Return the final answer (number of subsets with a sum equal to 0) return dp[n][maxSum]; } // Driver code static void Main() { int[] arr = { 2, 2, 2, -4, -4 }; int n = arr.Length; // Function call to find the number of subsets int result = SubsetCnt(arr, n); // Display the result Console.WriteLine(result); }} |
Output
7
Time Complexity: O(N*S), where N is the number of elements in the array, and S is the sum of all the elements.
Auxiliary Space: O(N*S)
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!
