Dada una array A[] que consta de N enteros no negativos y un entero K , la tarea es encontrar el número de formas en que los operadores ‘+’ y ‘-‘ se pueden colocar delante de los elementos de la array A[] tales que la suma de la array se convierte en K .
Ejemplos:
Entrada: A[] = {1, 1, 2, 3}, N = 4, K = 1
Salida: 3
Explicación: Las tres formas posibles son:
- + 1 + 1 + 2 – 3 = 1
- + 1 – 1 – 2 + 3 = 1
- – 1 + 1 – 1 + 3 = 1
Entrada: A[] = {1, 1, 1, 1, 1}, N = 5, K = 3
Salida: 5
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- Almacene la suma de elementos que tengan ‘+’ delante de ese elemento y ‘-‘ delante de ese elemento en variables, digamos P1 y P2 , de modo que la suma de la array se convierta en K .
- Almacene la suma total de la array A[] en una variable, digamos K .
- Por lo tanto, surgen las siguientes ecuaciones:
- P1 + P2 = suma
- P1 – P2 = K
- Resolviendo las ecuaciones anteriores se obtiene P1 = (suma + K) / 2 .
- Por lo tanto, el problema se ha transformado en encontrar el número de subconjuntos con suma P1 .
- Si un elemento de A es igual a 0 , los operadores ‘+’ y ‘-‘ funcionan en arreglos válidos, por lo tanto, los 0 pueden ignorarse de manera segura y calcularse por separado.
Por lo tanto, el problema se puede resolver utilizando Programación Dinámica . Siga los pasos a continuación para resolver el problema:
- Calcule y almacene la suma de elementos del arreglo A[] y el número de ceros en A[] en las variables suma y c respectivamente.
- Si K es mayor que sum o (sum + K) es impar, devuelve 0 .
- Agregue K a sum y divídalo por 2, es decir , sum = (sum + K) / 2 , que es la suma requerida. Encuentre el número de subconjuntos iguales a esa suma .
- Cree una array dp 2D de dimensiones N*sum . donde dp[i][j] representa el número de subconjuntos hasta i-1 que tienen suma j .
- Los casos base que se deben considerar son los siguientes:
- dp[0][i] = 0 , para 0 <= i <= sum , ya que no se ha considerado ningún elemento de la array A[]
- dp[i][0] = 1 , para 0 <= i <= N , ya que siempre es posible obtener una suma 0 .
- Iterar de 1 a N , y para cada índice actual i , realizar las siguientes operaciones:
- Iterar de 1 a suma y para cada índice actual j , realizar las siguientes transiciones:
- Si A[i – 1] es menor que j y A[i – 1] no es igual a 0 , establezca dp[i][j] = dp[i – 1][j] + dp[i – 1][ j-A[i-1]].
- De lo contrario, copie el estado anterior, es decir, dp[i][j] = dp[i – 1][j].
- Iterar de 1 a suma y para cada índice actual j , realizar las siguientes transiciones:
- Finalmente, devuelve el producto de dp[N][sum] y 2 c (para tener en cuenta los 0), es decir , dp[N][sum]*2 c .
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;
// Function to count number of ways
// '+' and '-' operators can be placed
// in front of array elements to make
// the sum of array elements equal to K
int solve(int A[], int N, int K)
{
// Stores sum of the array
int sum = 0;
// Stores count of 0s in A[]
int c = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += A[i];
// Update count of 0s
if (A[i] == 0)
c++;
}
// Conditions where no arrangements
// are possible which adds up to K
if (K > sum || (sum + K) % 2)
return 0;
// Required sum
sum = (sum + K) / 2;
// Dp array
int dp[N + 1][sum + 1];
// Base cases
for (int i = 0; i <= sum; i++)
dp[0][i] = 0;
for (int i = 0; i <= N; i++)
dp[i][0] = 1;
// Fill the dp array
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= sum; j++) {
if (A[i - 1] <= j && A[i - 1])
dp[i][j] = dp[i - 1][j]
+ dp[i - 1][j - A[i - 1]];
else
dp[i][j] = dp[i - 1][j];
}
}
// Return answer
return dp[N][sum] + pow(2, c);
}
// Driver Code
int main()
{
// Input
int A[] = { 1, 1, 2, 3 };
int N = sizeof(A) / sizeof(A[0]);
int K = 3;
// Function call
cout << solve(A, N, K) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count number of ways
// '+' and '-' operators can be placed
// in front of array elements to make
// the sum of array elements equal to K
static int solve(int A[], int N, int K)
{
// Stores sum of the array
int sum = 0;
// Stores count of 0s in A[]
int c = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += A[i];
// Update count of 0s
if (A[i] == 0)
c++;
}
// Conditions where no arrangements
// are possible which adds up to K
if ((K > sum) || (((sum + K) % 2) != 0))
return 0;
// Required sum
sum = (sum + K) / 2;
// Dp array
int dp[][] = new int[N + 1][sum + 1];
// Base cases
for (int i = 0; i <= sum; i++)
dp[0][i] = 0;
for (int i = 0; i <= N; i++)
dp[i][0] = 1;
// Fill the dp array
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= sum; j++) {
if ((A[i - 1] <= j) && (A[i - 1] != 0))
dp[i][j] = dp[i - 1][j]
+ dp[i - 1][j - A[i - 1]];
else
dp[i][j] = dp[i - 1][j];
}
}
// Return answer
return dp[N][sum] + (int)Math.pow(2, c);
}
// Driver Code
public static void main(String[] args)
{
// Input
int A[] = { 1, 1, 2, 3 };
int N = A.length;
int K = 3;
// Function call
System.out.print(solve(A, N, K));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach # Function to count number of ways # '+' and '-' operators can be placed # in front of array elements to make # the sum of array elements equal to K def solve(A, N, K): # Stores sum of the array sum = 0 # Stores count of 0s in A[] c = 0 # Traverse the array for i in range(N): # Update sum sum += A[i] # Update count of 0s if (A[i] == 0): c += 1 # Conditions where no arrangements # are possible which adds up to K if (K > sum or (sum + K) % 2): return 0 # Required sum sum = (sum + K) // 2 # Dp array dp = [[0 for i in range(sum + 1)] for j in range(N + 1)] # Base cases for i in range(sum + 1): dp[0][i] = 0 for i in range(N + 1): dp[i][0] = 1 # Fill the dp array for i in range(1, N + 1, 1): for j in range(1, sum + 1, 1): if (A[i - 1] <= j and A[i - 1]): dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - A[i - 1]]) else: dp[i][j] = dp[i - 1][j] # Return answer return dp[N][sum] + pow(2, c) # Driver Code if __name__ == '__main__': # Input A = [ 1, 1, 2, 3 ] N = len(A) K = 3 # Function call print(solve(A, N, K)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to count number of ways
// '+' and '-' operators can be placed
// in front of array elements to make
// the sum of array elements equal to K
static int solve(int[] A, int N, int K)
{
// Stores sum of the array
int sum = 0;
// Stores count of 0s in A[]
int c = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += A[i];
// Update count of 0s
if (A[i] == 0)
c++;
}
// Conditions where no arrangements
// are possible which adds up to K
if ((K > sum) || (((sum + K) % 2) != 0))
return 0;
// Required sum
sum = (sum + K) / 2;
// Dp array
int[, ] dp= new int[N + 1, sum + 1];
// Base cases
for (int i = 0; i <= sum; i++)
dp[0, i] = 0;
for (int i = 0; i <= N; i++)
dp[i,0] = 1;
// Fill the dp array
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= sum; j++) {
if ((A[i - 1] <= j) && (A[i - 1] != 0))
dp[i,j] = dp[i - 1,j]
+ dp[i - 1,j - A[i - 1]];
else
dp[i,j] = dp[i - 1,j];
}
}
// Return answer
return dp[N, sum] + (int)Math.Pow(2, c);
}
// Driver code
static public void Main ()
{
// Input
int[] A = { 1, 1, 2, 3 };
int N = A.Length;
int K = 3;
// Function call
Console.Write(solve(A, N, K));
}
}
// This code is contributed by offbeat
Javascript
<script>
// JavaScript program for the above approach
// Function to count number of ways
// '+' and '-' operators can be placed
// in front of array elements to make
// the sum of array elements equal to K
function solve(A, N, K)
{
// Stores sum of the array
let sum = 0;
// Stores count of 0s in A[]
let c = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
// Update sum
sum += A[i];
// Update count of 0s
if (A[i] == 0)
c++;
}
// Conditions where no arrangements
// are possible which adds up to K
if (K > sum || (sum + K) % 2)
return 0;
// Required sum
sum = (sum + K) / 2;
// Dp array
let dp = new Array(N + 1);
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(sum + 1);
}
// Base cases
for (let i = 0; i <= sum; i++)
dp[0][i] = 0;
for (let i = 0; i <= N; i++)
dp[i][0] = 1;
// Fill the dp array
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= sum; j++) {
if (A[i - 1] <= j && A[i - 1])
dp[i][j] = dp[i - 1][j]
+ dp[i - 1][j - A[i - 1]];
else
dp[i][j] = dp[i - 1][j];
}
}
// Return answer
return dp[N][sum] + Math.pow(2, c);
}
// Driver Code
// Input
let A = [1, 1, 2, 3];
let N = A.length;
let K = 3;
// Function call
document.write(solve(A, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de Tiempo: O(N * suma)
Espacio Auxiliar: O(N * suma)
Publicación traducida automáticamente
Artículo escrito por sonigurleen60 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA