Recuento de subconjuntos con suma igual a X – Part 1

Dada una array arr[] de longitud N y un entero X , la tarea es encontrar el número de subconjuntos con una suma igual a X.

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 3}, X = 6 
Salida: 3 
Todos los subconjuntos posibles son {1, 2, 3}, 
{1, 2, 3} y {3, 3}

Entrada: arr[] = {1, 1, 1, 1}, X = 1 
Salida: 4 

Enfoque: un enfoque simple es resolver este problema generando todos los subconjuntos posibles y luego verificando si el subconjunto tiene la suma requerida. Este enfoque tendrá una complejidad de tiempo exponencial. 

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

// Naive Approach
 
#include <stdio.h>
 
void printBool(int n, int len)
{
 
    while (n) {
        if (n & 1)
            printf("1 ");
        else
            printf("0 ");
 
        n >>= 1;
        len--;
    }
 
    // This is used for padding zeros
    while (len) {
        printf("0 ");
        len--;
    }
    printf("\n");
}
 
// Function
// Prints all the subsets of given set[]
void printSubsetsCount(int set[], int n, int val)
{
    int sum; // it stores the current sum
    int count = 0;
    for (int i = 0; i < (1 << n); i++) {
        sum = 0;
        // Print current subset
        for (int j = 0; j < n; j++)
 
            // (1<<j) is a number with jth bit 1
            // so when we 'and' them with the
            // subset number we get which numbers
            // are present in the subset and which are not
            // Refer :
            // https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/?ref=lbp
            if ((i & (1 << j)) > 0) {
                sum += set[j]; // elements are added one by
                               // one of a subset to the sum
            }
        // It checks if the sum is equal to desired sum. If
        // it is true then it prints the elements of the sum
        // to the output
        if (sum == val) {
            /*
             * Uncomment printBool(i,n) to get the boolean
             * representation of the selected elements from
             * set. For this example output of this
             * representation will be 0 1 1 1 0 // 2,3,4
             * makes sum 9 1 0 1 0 1 // 1,3,5 also makes sum
             * 9 0 0 0 1 1 // 4,5 also makes sum 9
             *
             * 'i' is used for 'and' operation so the
             * position of set bits in 'i' will be the
             * selected element. and as we have to give
             * padding with zeros to represent the complete
             * set , so length of the set ('n') is passed to
             * the function.
             * */
            //  printBool(i,n);
            count++;
        }
    }
    // it means no subset is found with given sum
    if (count == 0) {
        printf("No subset is found");
    }
    else {
        printf("%d", count);
    }
}
 
// Driver code
void main()
{
    int set[] = { 1, 2, 3, 4, 5 };
    printSubsetsCount(set, 5, 9);
}

3

Sin embargo, para valores más pequeños de X y elementos de array, este problema se puede resolver mediante programación dinámica . 
Veamos primero la relación de recurrencia. 

Este método es válido para todos los números enteros.

dp[i][C] = dp[i - 1][C - arr[i]] + dp[i - 1][C] 

Comprendamos el estado del DP ahora. Aquí, dp[i][C] almacena el número de subconjuntos del subarreglo arr[i…N-1] tal que su suma es igual a C . 
Por lo tanto, la recurrencia es muy trivial ya que solo hay dos opciones, es decir, considerar el i ^-ésimo elemento en el subconjunto o no.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define maxN 20
#define maxSum 50
#define minSum 50
#define base 50
 
// To store the states of DP
int dp[maxN][maxSum + minSum];
bool v[maxN][maxSum + minSum];
 
// Function to return the required count
int findCnt(int* arr, int i, int required_sum, int n)
{
    // Base case
    if (i == n) {
        if (required_sum == 0)
            return 1;
        else
            return 0;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][required_sum + base])
        return dp[i][required_sum + base];
 
    // Setting the state as solved
    v[i][required_sum + base] = 1;
 
    // Recurrence relation
    dp[i][required_sum + base]
        = findCnt(arr, i + 1, required_sum, n)
          + findCnt(arr, i + 1, required_sum - arr[i], n);
    return dp[i][required_sum + base];
}
 
// Driver code
int main()
{
    int arr[] = { 3, 3, 3, 3 };
    int n = sizeof(arr) / sizeof(int);
    int x = 6;
 
    cout << findCnt(arr, 0, x, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int maxN = 20;
static int maxSum = 50;
static int minSum = 50;
static int base = 50;
 
// To store the states of DP
static int [][]dp = new int[maxN][maxSum + minSum];
static boolean [][]v = new boolean[maxN][maxSum + minSum];
 
// Function to return the required count
static int findCnt(int []arr, int i,
                   int required_sum, int n)
{
    // Base case
    if (i == n)
    {
        if (required_sum == 0)
            return 1;
        else
            return 0;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][required_sum + base])
        return dp[i][required_sum + base];
 
    // Setting the state as solved
    v[i][required_sum + base] = true;
 
    // Recurrence relation
    dp[i][required_sum + base] =
          findCnt(arr, i + 1, required_sum, n) +
          findCnt(arr, i + 1, required_sum - arr[i], n);
    return dp[i][required_sum + base];
}
 
// Driver code
public static void main(String []args)
{
    int arr[] = { 3, 3, 3, 3 };
    int n = arr.length;
    int x = 6;
 
    System.out.println(findCnt(arr, 0, x, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
import numpy as np
 
maxN = 20
maxSum = 50
minSum = 50
base = 50
 
# To store the states of DP
dp = np.zeros((maxN, maxSum + minSum));
v = np.zeros((maxN, maxSum + minSum));
 
# Function to return the required count
def findCnt(arr, i, required_sum, n) :
 
    # Base case
    if (i == n) :
        if (required_sum == 0) :
            return 1;
        else :
            return 0;
 
    # If the state has been solved before
    # return the value of the state
    if (v[i][required_sum + base]) :
        return dp[i][required_sum + base];
 
    # Setting the state as solved
    v[i][required_sum + base] = 1;
 
    # Recurrence relation
    dp[i][required_sum + base] = findCnt(arr, i + 1,
                                         required_sum, n) + \
                                 findCnt(arr, i + 1,
                                         required_sum - arr[i], n);
     
    return dp[i][required_sum + base];
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 3, 3, 3 ];
    n = len(arr);
    x = 6;
 
    print(findCnt(arr, 0, x, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
 
static int maxN = 20;
static int maxSum = 50;
static int minSum = 50;
static int Base = 50;
 
// To store the states of DP
static int [,]dp = new int[maxN, maxSum + minSum];
static Boolean [,]v = new Boolean[maxN, maxSum + minSum];
 
// Function to return the required count
static int findCnt(int []arr, int i,
                   int required_sum, int n)
{
    // Base case
    if (i == n)
    {
        if (required_sum == 0)
            return 1;
        else
            return 0;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i, required_sum + Base])
        return dp[i, required_sum + Base];
 
    // Setting the state as solved
    v[i, required_sum + Base] = true;
 
    // Recurrence relation
    dp[i, required_sum + Base] =
          findCnt(arr, i + 1, required_sum, n) +
          findCnt(arr, i + 1, required_sum - arr[i], n);
    return dp[i,required_sum + Base];
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 3, 3, 3, 3 };
    int n = arr.Length;
    int x = 6;
 
    Console.WriteLine(findCnt(arr, 0, x, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
var maxN = 20
var maxSum = 50
var minSum = 50
var base = 50
 
// To store the states of DP
var dp = Array.from(Array(maxN),
()=>Array(maxSum+minSum));
var v = Array.from(Array(maxN),
()=>Array(maxSum+minSum));
 
// Function to return the required count
function findCnt(arr, i, required_sum, n)
{
    // Base case
    if (i == n) {
        if (required_sum == 0)
            return 1;
        else
            return 0;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][required_sum + base])
        return dp[i][required_sum + base];
 
    // Setting the state as solved
    v[i][required_sum + base] = 1;
 
    // Recurrence relation
    dp[i][required_sum + base]
        = findCnt(arr, i + 1,
          required_sum, n)
          + findCnt(arr, i + 1,
          required_sum - arr[i], n);
    return dp[i][required_sum + base];
}
 
// Driver code
var arr = [3, 3, 3, 3];
var n = arr.length;
var x = 6;
document.write( findCnt(arr, 0, x, n));
 
</script>

6

Método 2: Uso del método de tabulación:

This method is valid only for those arrays which contains positive elements.
In this method we use a 2D array of size (arr.size() + 1) * (target + 1) of type integer.
Initialization of Matrix:
mat[0][0] = 1 because If the size of sum is 

if (A[i] > j)
DP[i][j] = DP[i-1][j]
else 
DP[i][j] = DP[i-1][j] + DP[i-1][j-A[i]]

Esto significa que si el elemento actual tiene un valor mayor que el ‘valor de la suma actual’ copiaremos la respuesta para los casos anteriores

Y si el valor de la suma actual es mayor que el elemento ‘ésimo’, veremos si alguno de los estados anteriores ya ha experimentado la suma = ‘j’ y cualquier estado anterior experimentó un valor ‘j – A [i]’ que resolverá nuestro propósito

#include <bits/stdc++.h>
using namespace std;
 
int subsetSum(int a[], int n, int sum)
{
    // Initializing the matrix
    int tab[n + 1][sum + 1];
  // Initializing the first value of matrix
    tab[0][0] = 1;
    for (int i = 1; i <= sum; i++)
        tab[0][i] = 0;
     
   
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= sum; j++)
        {
          // if the value is greater than the sum
            if (a[i - 1] > j)
                tab[i][j] = tab[i - 1][j];
            else
            {
                tab[i][j] = tab[i - 1][j] + tab[i - 1][j - a[i - 1]];
            }
        }
    }
 
 
    return tab[n][sum];
}
 
int main()
{
    int n = 4;
    int a[] = {3,3,3,3};
    int sum = 6;
 
    cout << (subsetSum(a, n, sum));
}

import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
static int subsetSum(int a[], int n, int sum)
{
     
    // Initializing the matrix
    int tab[][] = new int[n + 1][sum + 1];
 
    // Initializing the first value of matrix
    tab[0][0] = 1;
 
    for(int i = 1; i <= sum; i++)
        tab[0][i] = 0;
 
 
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= sum; j++)
        {
             
            // If the value is greater than the sum
            if (a[i - 1] > j)
                tab[i][j] = tab[i - 1][j];
 
            else
            {
                tab[i][j] = tab[i - 1][j] +
                            tab[i - 1][j - a[i - 1]];
            }
        }
    }
 
    return tab[n][sum];
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 4;
    int a[] = { 3, 3, 3, 3 };
    int sum = 6;
 
    System.out.print(subsetSum(a, n, sum));
}
}
 
// This code is contributed by Kingash

def subset_sum(a: list, n: int, sum: int):
   
    # Initializing the matrix
    tab = [[0] * (sum + 1) for i in range(n + 1)]
    tab[0][0] = 1
    for i in range(1, sum + 1):
        tab[0][i] = 0
     
    for i in range(1, n+1):
        for j in range(sum + 1):
            if a[i-1] <= j:
                tab[i][j] = tab[i-1][j] + tab[i-1][j-a[i-1]]
            else:
                tab[i][j] = tab[i-1][j]
    return tab[n][sum]
 
if __name__ == '__main__':
    a = [3, 3, 3, 3]
    n = 4
    sum = 6
    print(subset_sum(a, n, sum))
 
    # This code is contributed by Premansh2001.

using System;
 
class GFG{
 
static int subsetSum(int []a, int n, int sum)
{
     
    // Initializing the matrix
    int [,]tab = new int[n + 1, sum + 1];
 
    // Initializing the first value of matrix
    tab[0, 0] = 1;
 
    for(int i = 1; i <= sum; i++)
        tab[0, i] = 0;
 
 
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= sum; j++)
        {
             
            // If the value is greater than the sum
            if (a[i - 1] > j)
                tab[i, j] = tab[i - 1, j];
            else
            {
                tab[i, j] = tab[i - 1, j] +
                            tab[i - 1, j - a[i - 1]];
            }
        }
    }
    return tab[n, sum];
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4;
    int []a = { 3, 3, 3, 3 };
    int sum = 6;
 
    Console.Write(subsetSum(a, n, sum));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
 
function subsetSum( a,  n, sum)
{
    // Initializing the matrix
    var tab = new Array(n + 1);
    for (let i = 0; i< n+1; i++)
      tab[i] = new Array(sum + 1);
  // Initializing the first value of matrix
    tab[0][0] = 1;
    for (let i = 1; i <= sum; i++)
        tab[0][i] = 0;
 
    for (let i = 1; i <= n; i++)
    {
        for (let j = 0; j <= sum; j++)
        {
          // if the value is greater than the sum
            if (a[i - 1] > j)
                tab[i][j] = tab[i - 1][j];
            else
            {
                tab[i][j] = tab[i - 1][j] + tab[i - 1][j - a[i - 1]];
            }
        }
    }
 
 
    return tab[n][sum];
}
 
var n = 4;
var a = new Array(3,3,3,3);
var sum = 6;
 
console.log(subsetSum(a, n, sum));
 
// This code is contributed by ukasp.
</script>

6

Complejidad de tiempo: O (suma * n), donde la suma es la ‘suma objetivo’ y ‘n’ es el tamaño de la array.
Espacio auxiliar: O(suma*n), como el tamaño de la array 2-D, es suma*n. 

Método 3: Optimización del espacio:

Podemos resolver este problema simplemente cuidando el último estado y el estado actual para que podamos resolver este problema en la complejidad del espacio O (objetivo + 1).

Ejemplo:-

vector<int> array = { 3, 3, 3, 3 }; con targetSum de 6;

dp[0][arr[0]] — informa sobre qué pasa si en el índice 0 necesitamos arr[0] para lograr el targetSum y, afortunadamente, tenemos esa solución, así que márquelos como 1;

===== pd[0][3]=1

objetivo Índice	0	1	2	3	4	5	6
0	1	0	0	1	0	0	0
1	1	0	0	2	0	0	1
2	1	0	0	3	0	0	3
3	1	0	0	4	0	0	6

at dp[2][6] --- tells tell me is at index 2 can count some subsets with sum=6, How can we achieve this?
so we can tell ok i have reached at index 2 by adding element of index 1 or not both case has been added ------ means dp[i-1] we need only bcoz we are need of last index decision only nothing more than that so this why we are using a huge 2D array
just store our running state and last state that's it.

1.Time Complexity:- O(N*val)
2.Space Complexity:- O(Val)
where val and n are targetSum and number of element.

#include <bits/stdc++.h>
using namespace std;
 
int CountSubsetSum(vector<int>& arr, int val, int n)
{
    int count = 0;
    vector<int> PresentState(val + 1, 0),
        LastState(val + 1, 0);
    // consider only last and present state we dont need the
    // (present-2)th state and above and we know for val to
    // be 0 if we dont pick the current index element we can
    // achieve
    PresentState[0] = LastState[0] = 1;
    if (arr[0] <= val)
        LastState[arr[0]] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= val; j++)
            PresentState[j]
                = ((j >= arr[i]) ? LastState[j - arr[i]]
                                 : 0)
                  + LastState[j];
        // this we will need in the next iteration so just
        // swap current and last state.
        LastState = PresentState;
    }
    // Note after exit from loop we will having a present
    // state which is nothing but the laststate itself;
    return PresentState[val]; // or return
                              // CurrentState[val];
}
int main()
{
    vector<int> arr = { 3, 3, 3, 3 };
    cout << CountSubsetSum(arr, 6, arr.size());
}

import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
    static int subsetSum(int arr[], int n, int val)
    {
 
        int[] LastState = new int[val + 1];
        // consider only last and present state we dont need
        // the (present-2)th state and above and we know for
        // val to be 0 if we dont pick the current index
        // element we can achieve
 
        LastState[0] = 1;
        if (arr[0] <= val) {
            LastState[arr[0]] = 1;
        }
        for (int i = 1; i < n; i++) {
            int[] PresentState = new int[val + 1];
            PresentState[0] = 1;
            for (int j = 1; j <= val; j++) {
 
                int notPick = LastState[j];
                int pick = 0;
                if (arr[i] <= j)
                    pick = LastState[j - arr[i]];
 
                PresentState[j] = pick + notPick;
            }
            // this we will need in the next iteration so
            // just swap current and last state.
            LastState = PresentState;
        }
        // Note after exit from loop we will having a
        // present state which is nothing but the laststate
        // itself;
        return LastState[val]; // or return
                               // CurrentState[val];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        int a[] = { 3, 3, 3, 3 };
        int sum = 6;
 
        System.out.print(subsetSum(a, n, sum));
    }
}
 
// This code is contributed by Sanskar

// C# implementation of the approach
using System;
using System.Collections.Generic;           
 
class GFG
{
 
  static int subsetSum(int[] arr, int n, int val)
  {
 
    int[] LastState = new int[val + 1];
    // consider only last and present state we dont need
    // the (present-2)th state and above and we know for
    // val to be 0 if we dont pick the current index
    // element we can achieve
 
    LastState[0] = 1;
    if (arr[0] <= val) {
      LastState[arr[0]] = 1;
    }
    for (int i = 1; i < n; i++) {
      int[] PresentState = new int[val + 1];
      PresentState[0] = 1;
      for (int j = 1; j <= val; j++) {
 
        int notPick = LastState[j];
        int pick = 0;
        if (arr[i] <= j)
          pick = LastState[j - arr[i]];
 
        PresentState[j] = pick + notPick;
      }
      // this we will need in the next iteration so
      // just swap current and last state.
      LastState = PresentState;
    }
    // Note after exit from loop we will having a
    // present state which is nothing but the laststate
    // itself;
    return LastState[val]; // or return
    // CurrentState[val];
  }
 
  // Driver code
  public static void Main (String[] args)
  {
    int n = 4;
    int[] a = { 3, 3, 3, 3 };
    int sum = 6;
 
    Console.WriteLine(subsetSum(a, n, sum));
  }
}
 
// This code is contributed by sanjoy_62.

6

Complejidad de tiempo: O (suma * n), donde la suma es la ‘suma objetivo’ y ‘n’ es el tamaño de la array.
Espacio Auxiliar: O(suma).