Cuente las formas de dividir la array en un par de subconjuntos con una diferencia entre su suma igual a K

Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar el número de formas de dividir la array en un par de subconjuntos de modo que la diferencia entre su suma sea K .

Ejemplos:

Entrada: arr[] = {1, 1, 2, 3}, K = 1
Salida: 3
Explicación:
Las siguientes divisiones en un par de subconjuntos satisfacen la condición dada:  

1. {1, 1, 2}, {3}, diferencia = (1 + 1 + 2) – 3 = 4 – 3 = 1.
2. {1, 3} {1, 2}, diferencia = (1 + 3) – (1 + 2) = 4 – 3 = 1.
3. {1, 3} {1, 2}, diferencia = (1 + 3) – (1 + 2) = 4 – 3 = 1.

Por lo tanto, la cuenta de formas de dividir es 3.
 

Entrada: arr[] = {1, 2, 3}, K = 2
Salida: 1
Explicación:
La única división posible en un par de subconjuntos que satisfacen la condición dada es {1, 3}, {2}, donde la diferencia = (1 + 3) – 2 = 4 – 2 =2. 
Por lo tanto, la cuenta de formas de dividir es 1. 

Enfoque ingenuo: el enfoque simple para resolver el problema dado es generar todos los subconjuntos posibles y almacenar la suma de cada subconjunto en una array, digamos subset[] . Luego, verifique si existe algún par en el subconjunto de la array [] cuya diferencia es K . Después de comprobar todos los pares, imprima el recuento total de dichos pares como resultado. 
Complejidad de Tiempo: O(2 ^N )
Espacio Auxiliar: O(2 ^N )

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando las siguientes observaciones.

Sea la suma del primer y segundo subconjunto S1 y S2 respectivamente, y la suma de los elementos del arreglo sea Y .

Ahora, la suma de ambos subconjuntos debe ser igual a la suma de los elementos de la array. 
Por tanto, S1 + S2 = Y — (1)
Para satisfacer la condición dada, su diferencia debe ser igual a K .
Por lo tanto, S1 – S2 = K — (2)
Sumando (1) y (2), la ecuación obtenida es 
S1 = (K + Y)/2 — (3)

Por lo tanto, para un par de subconjuntos que tienen sumas S1 y S2 , la ecuación (3) debe cumplirse, es decir, la suma de los elementos del subconjunto debe ser igual a (K + Y)/2 . Ahora, el problema se reduce a contar el número de subconjuntos con una suma dada . Este problema se puede resolver utilizando Programación Dinámica , cuya relación de recurrencia es la siguiente:

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

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 del arreglo en el subconjunto o no.

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

// C++ program for the above 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 find count of subsets
// with a given sum
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 an already computed
    // subproblem occurs
    if (v[i][required_sum + base])
        return dp[i][required_sum + base];
 
    // Set 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];
}
 
// Function to count ways to split array into
// pair of subsets with difference K
void countSubsets(int* arr, int K,
                  int n)
{
 
    // Store the total sum of
    // element of the array
    int sum = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // Calculate sum of array elements
        sum += arr[i];
    }
 
    // Store the required sum
    int S1 = (sum + K) / 2;
 
    // Print the number of subsets
    // with sum equal to S1
    cout << findCnt(arr, 0, S1, n);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 2, 3 };
    int N = sizeof(arr) / sizeof(int);
    int K = 1;
 
    // Function Call
    countSubsets(arr, K, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
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 find count of subsets
  // with a given sum
  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 an already computed
    // subproblem occurs
    if (v[i][required_sum + Base])
      return dp[i][required_sum + Base];
 
    // Set 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];
  }  
 
  // Function to count ways to split array into
  // pair of subsets with difference K
  static void countSubsets(int[] arr, int K,
                           int n)
  {
    // Store the total sum of
    // element of the array
    int sum = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++)
    {
 
      // Calculate sum of array elements
      sum += arr[i];
    }
 
    // Store the required sum
    int S1 = (sum + K) / 2;
 
    // Print the number of subsets
    // with sum equal to S1
    System.out.print(findCnt(arr, 0, S1, n));
  } 
 
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 1, 1, 2, 3 };
    int N = arr.length;
    int K = 1;
 
    // Function Call
    countSubsets(arr, K, N);
  }
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
maxN = 20;
maxSum = 50;
minSum = 50;
Base = 50;
 
# To store the states of DP
dp = [[0 for i in range(maxSum + minSum)] for j in range(maxN)];
v = [[False for i in range(maxSum + minSum)] for j in range(maxN)];
 
# Function to find count of subsets
# with a given sum
def findCnt(arr, i, required_sum, n):
   
    # Base case
    if (i == n):
        if (required_sum == 0):
            return 1;
        else:
            return 0;
 
    # If an already computed
    # subproblem occurs
    if (v[i][required_sum + Base]):
        return dp[i][required_sum + Base];
 
    # Set 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];
 
# Function to count ways to split array into
# pair of subsets with difference K
def countSubsets(arr, K, n):
   
    # Store the total sum of
    # element of the array
    sum = 0;
 
    # Traverse the array
    for i in range(n):
       
        # Calculate sum of array elements
        sum += arr[i];
 
    # Store the required sum
    S1 = (sum + K) // 2;
 
    # Print the number of subsets
    # with sum equal to S1
    print(findCnt(arr, 0, S1, n));
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 1, 2, 3];
    N = len(arr);
    K = 1;
 
    # Function Call
    countSubsets(arr, K, N);
 
    # This code is contributed by shikhasingrajput

// C# program for the above 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 bool[,] v = new bool[maxN, maxSum + minSum];
       
    // Function to find count of subsets
    // with a given sum
    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 an already computed
        // subproblem occurs
        if (v[i, required_sum + Base])
            return dp[i, required_sum + Base];
       
        // Set 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];
    }
       
    // Function to count ways to split array into
    // pair of subsets with difference K
    static void countSubsets(int[] arr, int K,
                      int n)
    {
       
        // Store the total sum of
        // element of the array
        int sum = 0;
       
        // Traverse the array
        for (int i = 0; i < n; i++)
        {
       
            // Calculate sum of array elements
            sum += arr[i];
        }
       
        // Store the required sum
        int S1 = (sum + K) / 2;
       
        // Print the number of subsets
        // with sum equal to S1
        Console.Write(findCnt(arr, 0, S1, n));
    }  
 
  // Driver code
  static void Main()
  {
    int[] arr = { 1, 1, 2, 3 };
    int N = arr.Length;
    int K = 1;
   
    // Function Call
    countSubsets(arr, K, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// Javascript program for the above 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 find count of subsets
// with a given sum
function findCnt(arr, i, required_sum, n)
{
    // Base case
    if (i == n) {
        if (required_sum == 0)
            return 1;
        else
            return 0;
    }
 
    // If an already computed
    // subproblem occurs
    if (v[i][required_sum + base])
        return dp[i][required_sum + base];
 
    // Set 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];
}
 
// Function to count ways to split array into
// pair of subsets with difference K
function countSubsets(arr, K, n)
{
 
    // Store the total sum of
    // element of the array
    var sum = 0;
 
    // Traverse the array
    for (var i = 0; i < n; i++) {
 
        // Calculate sum of array elements
        sum += arr[i];
    }
 
    // Store the required sum
    var S1 = (sum + K) / 2;
 
    // Print the number of subsets
    // with sum equal to S1
    document.write( findCnt(arr, 0, S1, n));
}
 
// Driver Code
var arr = [ 1, 1, 2, 3 ];
var N = arr.length;
var K = 1;
// Function Call
countSubsets(arr, K, N);
 
 
</script>

3

Complejidad temporal: O(N*K) 
Espacio auxiliar: O(N*K)