Número de subconjuntos con suma cero

Dada una array ‘arr’ que consta de números enteros, la tarea es encontrar el número de subconjuntos tales que su suma sea igual a cero. También se debe considerar el subconjunto vacío.

Ejemplos: 

Entrada: arr[] = {2, 2, -4} 
Salida: 2 
Todos los subconjuntos posibles: 
{} = 0 
{2} = 2 
{2} = 2 
{-4} = -4 
{2, 2} = 4 
{ 2, -4} = -2 
{2, -4} = -4 
{2, 2, -4} = 0 
Dado que {} y {2, 2, -4} son solo subconjuntos posibles 
con suma 0, y sea ​​2.
Entrada: arr[] = {1, 1, 1, 1} 
Salida: 1 
{} es el único subconjunto posible con 
suma 0, por lo que ans es igual a 1.  

Un enfoque simple es generar todos los subconjuntos posibles de forma recursiva y contar el número de subconjuntos con una suma igual a 0. La complejidad temporal de este enfoque será O(2^n).

Un mejor enfoque será el uso de la programación dinámica . 
Supongamos que la suma de todos los elementos que hemos seleccionado hasta el índice ‘i-1’ es ‘S’. Entonces, comenzando desde el índice ‘i’, tenemos que encontrar el número de subconjuntos del subarreglo {i, N-1} con suma igual a -S. 
Definamos dp[i][S]. Significa el número del subconjunto del subarreglo {i, N-1} de ‘arr’ con suma igual a ‘-S’. 
Si estamos en i-ésimo índice, tenemos dos opciones, es decir, incluirlo en la suma o dejarlo. 
Por lo tanto, la relación de recurrencia requerida se convierte en 

dp[i][s] = dp[i+1][s+arr[i]] + dp[i+1][s] 

A continuación se muestra la implementación del enfoque anterior:  

#include <bits/stdc++.h>
#define maxSum 100
#define arrSize 51
using namespace std;
 
// variable to store
// states of dp
int 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 positive
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 + 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 function
int main()
{
    int arr[] = { 2, 2, 2, -4, -4 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << SubsetCnt(0, 0, arr, n);
}

// Java implementation of above approach
class 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 implementation of above approach
import numpy as np
 
maxSum = 100
arrSize = 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 Code
if __name__ == "__main__" :
 
    arr = [ 2, 2, 2, -4, -4 ];
    n = len(arr);
 
    print(SubsetCnt(0, 0, arr, n));
 
# This code is contributed by AnkitRai01

// C# implementation of above approach
using 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..

<script>
 
var maxSum = 100
var arrSize = 51
 
// variable to store
// states of dp
var 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 positive
function 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 function
var arr = [2, 2, 2, -4, -4];
var n = arr.length;
document.write( SubsetCnt(0, 0, arr, n));
 
</script>

7

Complejidad de tiempo: O(n*S), donde n es el número de elementos en la array y S es la suma de todos los elementos.