Conteo de subconjuntos con suma igual a X usando Recursión

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 usando recursividad .
Ejemplos: 
 

Entrada: arr[] = {2, 3, 5, 6, 8, 10}, X = 10 
Salida: 3 
Explicación: 
Todos los subconjuntos posibles con suma 10 son {2, 3, 5}, {2, 8}, { 10}
Entrada: arr[] = {1, 2, 3, 4, 5}, X = 7 
Salida: 3 
Explicación: 
Todos los subconjuntos posibles con suma 7 son {2, 5}, {3, 4}, {1, 2, 4} 
 

Enfoque: La idea es verificar recursivamente todos los subconjuntos. Si algún subconjunto tiene la suma igual a N, entonces incremente el conteo en 1. De lo contrario, continúe. 
Para formar un subconjunto, hay dos casos para cada elemento: 
 

• Incluir el elemento en el conjunto.
• Excluye el elemento en el conjunto.

Por lo tanto, se pueden seguir los siguientes pasos para calcular la respuesta: 
 

1. Obtenga la array para la cual se encuentran los subconjuntos con la suma igual a K.
2. Cuente recursivamente los subconjuntos con la suma igual a K de la siguiente manera:
   • Caso base: el caso base será cuando se haya alcanzado el final de la array. Si aquí la suma se ha encontrado como X, entonces aumente la cuenta del subconjunto en 1. Devuelva la cuenta evaluada en la condición base.

if (n == 0) {
    if (sum == s)
        count++;
    return count;
}

• Llamada recursiva: si el caso base no se satisface, llame a la función dos veces. Una vez al incluir el elemento en el índice ‘i’ y una vez al no incluir el elemento. Encuentre el conteo para ambos casos y luego devuelva el conteo final.

count = subsetSum(arr, n, sum , s , count);
count = subsetSum(arr, n, sum, s + arr[n-1 count);

• Declaración de devolución: en cada paso, se devuelve el recuento de subconjuntos al incluir un elemento en particular o al no incluir un elemento en particular. Finalmente, cuando se ejecuta toda la pila de recursividad, se devuelve el recuento total.

Del enfoque anterior, se puede analizar claramente que si hay N elementos en la array, entonces surgen un total de 2 ^N casos. Cada elemento de la array se comprueba en los casos anteriores mediante recursividad . 
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to print the count of
// subsets with sum equal to the given value X
 
#include <iostream>
using namespace std;
 
// Recursive function to return the count
// of subsets with sum equal to the given value
int subsetSum(int arr[], int n, int i,
              int sum, int count)
{
    // The recursion is stopped at N-th level
    // where all the subsets of the given array
    // have been checked
    if (i == n) {
 
        // Incrementing the count if sum is
        // equal to 0 and returning the count
        if (sum == 0) {
            count++;
        }
        return count;
    }
 
    // Recursively calling the function for two cases
    // Either the element can be counted in the subset
    // If the element is counted, then the remaining sum
    // to be checked is sum - the selected element
    // If the element is not included, then the remaining sum
    // to be checked is the total sum
    count = subsetSum(arr, n, i + 1, sum - arr[i], count);
    count = subsetSum(arr, n, i + 1, sum, count);
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int sum = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << subsetSum(arr, n, 0, sum, 0);
}

// Java program to print the count of
// subsets with sum equal to the given value X
import java.util.*;
 
class GFG {
 
    // Recursive function to return the count
    // of subsets with sum equal to the given value
    static int subsetSum(int arr[], int n, int sum, int s,
                         int count)
    {
       
        // The recursion is stopped at N-th level
        // where all the subsets of the given array
        // have been checked
        if (n == 0) {
 
            // Incrementing the count if sum is
            // equal to the subset and returning the count
            if (sum == s) {
                count++;
            }
            return count;
        }
 
        count = subsetSum(arr, n - 1, sum, s, count);
        count = subsetSum(arr, n - 1, sum, s + arr[n - 1],
                          count);
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int sum = 10;
        int s = 0; // Initially assigning the sum of subset
                   // to be zero
        int n = arr.length;
 
        System.out.print(subsetSum(arr, n, sum, s, 0));
    }
}
 
// This code is contributed by Sparsh Choudhary
// (sparsht123t)

# Python3 program to print the count of
# subsets with sum equal to the given value X
 
# Recursive function to return the count
# of subsets with sum equal to the given value
def subsetSum(arr, n, i,sum, count):
     
    # The recursion is stopped at N-th level
    # where all the subsets of the given array
    # have been checked
    if (i == n):
 
        # Incrementing the count if sum is
        # equal to 0 and returning the count
        if (sum == 0):
            count += 1
        return count
 
    # Recursively calling the function for two cases
    # Either the element can be counted in the subset
    # If the element is counted, then the remaining sum
    # to be checked is sum - the selected element
    # If the element is not included, then the remaining sum
    # to be checked is the total sum
    count = subsetSum(arr, n, i + 1, sum - arr[i], count)
    count = subsetSum(arr, n, i + 1, sum, count)
    return count
 
# Driver code
arr = [1, 2, 3, 4, 5]
sum = 10
n = len(arr)
 
print(subsetSum(arr, n, 0, sum, 0))
 
# This code is contributed by mohit kumar 29

// C# program to print the count of
// subsets with sum equal to the given value X
using System;
 
class GFG
{
 
// Recursive function to return the count
// of subsets with sum equal to the given value
static int subsetSum(int []arr, int n, int i,
                    int sum, int count)
{
    // The recursion is stopped at N-th level
    // where all the subsets of the given array
    // have been checked
    if (i == n)
    {
 
        // Incrementing the count if sum is
        // equal to 0 and returning the count
        if (sum == 0)
        {
            count++;
        }
        return count;
    }
 
    // Recursively calling the function for two cases
    // Either the element can be counted in the subset
    // If the element is counted, then the remaining sum
    // to be checked is sum - the selected element
    // If the element is not included, then the remaining sum
    // to be checked is the total sum
    count = subsetSum(arr, n, i + 1, sum - arr[i], count);
    count = subsetSum(arr, n, i + 1, sum, count);
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5 };
    int sum = 10;
    int n = arr.Length;
 
    Console.Write(subsetSum(arr, n, 0, sum, 0));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript program to print the count of
// subsets with sum equal to the given value X
 
// Recursive function to return the count
// of subsets with sum equal to the given value
function subsetSum(arr, n, i, sum, count)
{
    // The recursion is stopped at N-th level
    // where all the subsets of the given array
    // have been checked
    if (i == n) {
 
        // Incrementing the count if sum is
        // equal to 0 and returning the count
        if (sum == 0) {
            count++;
        }
        return count;
    }
 
    // Recursively calling the function for two cases
    // Either the element can be counted in the subset
    // If the element is counted, then the remaining sum
    // to be checked is sum - the selected element
    // If the element is not included, then the remaining sum
    // to be checked is the total sum
    count = subsetSum(arr, n, i + 1, sum - arr[i], count);
    count = subsetSum(arr, n, i + 1, sum, count);
    return count;
}
 
// Driver code
var arr = [1, 2, 3, 4, 5];
var sum = 10;
var n = arr.length;
document.write( subsetSum(arr, n, 0, sum, 0));
 
</script>

3

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )

Enfoque Eficiente: En  este artículo
se ha discutido un método eficiente para resolver el problema usando Programación Dinámica .