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, 2}, {3}, diferencia = (1 + 1 + 2) – 3 = 4 – 3 = 1.
- {1, 3} {1, 2}, diferencia = (1 + 3) – (1 + 2) = 4 – 3 = 1.
- {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++
// 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
// 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.
Python3
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por ahujaanmol1289 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA