Dada una array arr[] que tiene N enteros. La tarea es determinar si la array se puede dividir en 3 subsecuencias de igual suma o no. En caso afirmativo, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {1, 1, 1}
Salida: Sí
Explicación:
Aquí la array se puede dividir en 3 sumas iguales. {1}Entrada: arr[] = {40}
Salida: No
Explicación:
Aquí la array no se puede dividir en 3 sumas iguales.
Enfoque recursivo: este problema se puede resolver usando recursividad . A continuación se muestran los pasos:
- Inicialice tres variables sum1 , sum2 y sum3 al valor 0.
- Luego, cada elemento de la array arr[] se agrega a cualquiera de estas 3 variables, lo que da todas las combinaciones posibles.
- En caso de que las subsecuencias tengan 3 sumas iguales, la array se puede dividir.
- Si la array se puede particionar, imprima » Sí» , de lo contrario, imprima » No» .
C++
// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
int checkEqualSumUtil(int arr[], int N,
int sm1, int sm2,
int sm3, int j)
{
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
else
{
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(arr, N,
sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Return maximum value among
// all above 3 recursive call
return max(max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
void checkEqualSum(int arr[], int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0)== 1)
{
cout << "Yes";
}
else
{
cout << "No";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = {17, 34, 59, 23, 17, 67,
57, 2, 18, 59, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
checkEqualSum(arr, N);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
static int checkEqualSumUtil(int arr[], int N,
int sm1, int sm2,
int sm3, int j)
{
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
else
{
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(arr, N,
sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Return maximum value among
// all above 3 recursive call
return Math.max(Math.max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
static void checkEqualSum(int arr[], int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1)
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = {17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1};
int N = arr.length;
// Function Call
checkEqualSum(arr, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach
# Utility function to check array can
# be partition to 3 subsequences of
# equal sum or not
def checkEqualSumUtil(arr, N, sm1, sm2, sm3, j):
# Base case
if j == N:
if sm1 == sm2 and sm2 == sm3:
return 1
else:
return 0
else:
# When element at index
# j is added to sm1
l = checkEqualSumUtil(arr, N, sm1 + arr[j],
sm2, sm3, j + 1)
# When element at index
# j is added to sm2
m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1)
# When element at index
# j is added to sm3
r = checkEqualSumUtil(arr, N, sm1,
sm2, sm3 + arr[j],
j + 1)
# Return maximum value among
# all above 3 recursive call
return max(l, m, r)
# Function to check array can be
# partition to 3 subsequences of
# equal sum or not
def checkEqualSum(arr, N):
# Initialise 3 sums to 0
sum1 = sum2 = sum3 = 0
# Function call
if checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1:
print("Yes")
else:
print("No")
# Driver code
# Given array arr[]
arr = [ 17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1 ]
N = len(arr)
# Function call
checkEqualSum(arr, N)
# This code is contributed by Stuti Pathak
C#
// C# program for
// the above approach
using System;
class GFG{
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
static int checkEqualSumUtil(int[] arr, int N,
int sm1, int sm2,
int sm3, int j)
{
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
else
{
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(arr, N,
sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(arr, N,
sm1, sm2,
sm3 + arr[j],
j + 1);
// Return maximum value among
// all above 3 recursive call
return Math.Max(Math.Max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
static void checkEqualSum(int[] arr, int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1)
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main()
{
// Given array arr[]
int[] arr = {17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1};
int N = arr.Length;
// Function Call
checkEqualSum(arr, N);
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Java script program for
// the above approach
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
function checkEqualSumUtil( arr, N,
sm1, sm2,
sm3, j)
{
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
else
{
// When element at index
// j is added to sm1
let l = checkEqualSumUtil(arr, N,
sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
let m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
let r = checkEqualSumUtil(arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Return maximum value among
// all above 3 recursive call
return Math.max(Math.max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
function checkEqualSum(arr,N)
{
// Initialise 3 sums to 0
let sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1)
{
document.write("Yes");
}
else
{
document.write("No");
}
}
// Driver Code
// Given array arr[]
let arr = [17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1];
let N = arr.length;
// Function Call
checkEqualSum(arr, N);
// This code is contributed by sravan kumar
</script>
Producción:
Yes
Complejidad de Tiempo: O(3 N )
Espacio Auxiliar: O(1)
Enfoque de programación dinámica : este problema se puede resolver mediante programación dinámica, la idea es almacenar todos los valores de los subproblemas superpuestos en un mapa y utilizar el valor de la subestructura superpuesta para reducir el número de llamadas recursivas. A continuación se muestran los pasos:
- Sean suma1 , suma2 y suma3 las tres sumas iguales que se van a dividir.
- Crea un mapa dp que tenga la clave.
- Recorre la array dada y haz lo siguiente:
- Caso base: mientras recorremos la array, si llegamos al final de la array, verifique si el valor de sum1 , sum2 y sum3 son iguales y luego devuelva 1 que garantizará que podamos dividir la array dada en una subsecuencia de igual valor de suma. De lo contrario, devuelve 0.
- Llamada recursiva: para cada elemento de la array, incluya cada elemento en sum1 , sum2 y sum3 uno por uno y devuelva el máximo de estas llamadas recursivas.
a = función_recursiva(array, N, suma1 + array[j], suma2, suma3, j + 1)
b = función_recursiva(array, N, suma1, suma2 + array[j], suma3, j + 1)
c = función_recursiva( array, N, suma1, suma2, suma3 + array[j], j + 1)
- Declaración de devolución: en la llamada recursiva anterior, el máximo de los tres valores dará el resultado de la llamada recursiva actual. Actualice el estado actual en la tabla dp como:
string s = a_string(suma1) + ‘_’ + a_string(suma2) + a_string(j)
return dp[s] = max(a, max(b, c) )
- Si puede haber una partición posible, imprima «Sí» , de lo contrario, imprima «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;
map<string, int> dp;
// Function to check array can be
// partition into sum of 3 equal
int checkEqualSumUtil(int arr[], int N,
int sm1,
int sm2,
int sm3, int j)
{
string s = to_string(sm1)
+ "_" + to_string(sm2)
+ to_string(j);
// Base Case
if (j == N) {
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
// If value at particular index is not
// -1 then return value at that index
// which ensure no more further calls
if (dp.find(s) != dp.end())
return dp[s];
else {
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(
arr, N, sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(
arr, N, sm1, sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(
arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Update the current state and
// return that value
return dp[s] = max(max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
void checkEqualSum(int arr[], int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(
arr, N, sum1,
sum2, sum3, 0)
== 1) {
cout << "Yes";
}
else {
cout << "No";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[]
= { 17, 34, 59, 23, 17, 67,
57, 2, 18, 59, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
checkEqualSum(arr, N);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static HashMap<String,
Integer> dp = new HashMap<String,
Integer>();
// Function to check array can be
// partition into sum of 3 equal
static int checkEqualSumUtil(int arr[], int N,
int sm1, int sm2,
int sm3, int j)
{
String s = String.valueOf(sm1) + "_" +
String.valueOf(sm2) + String.valueOf(j);
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
// If value at particular index is not
// -1 then return value at that index
// which ensure no more further calls
if (dp.containsKey(s))
return dp.get(s);
else
{
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(arr, N, sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Update the current state and
// return that value
dp.put(s, Math.max(Math.max(l, m), r));
return dp.get(s);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
static void checkEqualSum(int arr[], int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1)
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = {17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1};
int N = arr.length;
// Function Call
checkEqualSum(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
dp = {}
# Function to check array can be
# partition into sum of 3 equal
def checkEqualSumUtil(arr, N, sm1, sm2, sm3, j):
s = str(sm1) + "_" + str(sm2) + str(j)
# Base Case
if j == N:
if sm1 == sm2 and sm2 == sm3:
return 1
else:
return 0
# If value at particular index is not
# -1 then return value at that index
# which ensure no more further calls
if s in dp:
return dp[s]
# When element at index
# j is added to sm1
l = checkEqualSumUtil(arr, N, sm1 + arr[j],
sm2, sm3, j + 1)
# When element at index
# j is added to sm2
m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j], sm3,
j + 1)
# When element at index
# j is added to sm3
r = checkEqualSumUtil(arr, N, sm1,
sm2, sm3 + arr[j],
j + 1)
# Update the current state and
# return that value
dp[s] = max(l, m, r)
return dp[s]
# Function to check array can be
# partition to 3 subsequences of
# equal sum or not
def checkEqualSum(arr, N):
# Initialise 3 sums to 0
sum1 = sum2 = sum3 = 0
# Function Call
if checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1:
print("Yes")
else:
print("No")
# Driver code
# Given array arr[]
arr = [ 17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1 ]
N = len(arr)
# Function call
checkEqualSum(arr, N)
# This code is contributed by Stuti Pathak
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static Dictionary<string,
int> dp = new Dictionary<string,
int>();
// Function to check array can be
// partition into sum of 3 equal
static int checkEqualSumUtil(int []arr, int N,
int sm1, int sm2,
int sm3, int j)
{
string s = sm1.ToString() + "_" +
sm2.ToString() + j.ToString();
// Base Case
if (j == N)
{
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
// If value at particular index is not
// -1 then return value at that index
// which ensure no more further calls
if (dp.ContainsKey(s))
return dp[s];
else
{
// When element at index
// j is added to sm1
int l = checkEqualSumUtil(arr, N, sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
int m = checkEqualSumUtil(arr, N, sm1,
sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
int r = checkEqualSumUtil(arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Update the current state and
// return that value
dp[s] = Math.Max(Math.Max(l, m), r);
return dp[s];
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
static void checkEqualSum(int []arr, int N)
{
// Initialise 3 sums to 0
int sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function call
if (checkEqualSumUtil(arr, N, sum1,
sum2, sum3, 0) == 1)
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int []arr = { 17, 34, 59, 23, 17,
67, 57, 2, 18, 59, 1 };
int N = arr.Length;
// Function call
checkEqualSum(arr, N);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program for the above approach
var dp = new Map();
// Function to check array can be
// partition into sum of 3 equal
function checkEqualSumUtil(arr, N, sm1, sm2, sm3, j)
{
var s = (sm1.toString())
+ "_" + (sm2.toString())
+ (j.toString());
// Base Case
if (j == N) {
if (sm1 == sm2 && sm2 == sm3)
return 1;
else
return 0;
}
// If value at particular index is not
// -1 then return value at that index
// which ensure no more further calls
if (dp.has(s))
return dp[s];
else {
// When element at index
// j is added to sm1
var l = checkEqualSumUtil(
arr, N, sm1 + arr[j],
sm2, sm3, j + 1);
// When element at index
// j is added to sm2
var m = checkEqualSumUtil(
arr, N, sm1, sm2 + arr[j],
sm3, j + 1);
// When element at index
// j is added to sm3
var r = checkEqualSumUtil(
arr, N, sm1, sm2,
sm3 + arr[j], j + 1);
// Update the current state and
// return that value
return dp[s] = Math.max(Math.max(l, m), r);
}
}
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
function checkEqualSum(arr, N)
{
// Initialise 3 sums to 0
var sum1, sum2, sum3;
sum1 = sum2 = sum3 = 0;
// Function Call
if (checkEqualSumUtil(
arr, N, sum1,
sum2, sum3, 0)
== 1) {
document.write( "Yes");
}
else {
document.write( "No");
}
}
// Driver Code
// Given array arr[]
var arr
= [17, 34, 59, 23, 17, 67,
57, 2, 18, 59, 1];
var N = arr.length;
// Function Call
checkEqualSum(arr, N);
</script>
Producción:
Yes
Complejidad de tiempo: O(N*K 2 )
Espacio auxiliar: O(N*K 2 ) donde K es la suma de la array.
( a_string (suma1) + “_” + a_string (suma2) + “_” + a_string (suma3))
- con valor es 1 si se encuentran 3 subconjuntos iguales, de lo contrario el valor es 0 .
Publicación traducida automáticamente
Artículo escrito por sourav_singh_rajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA