Dada una array arr[] de enteros, la tarea es encontrar todas las formas posibles de dividir la array en dos subsecuencias de modo que la suma de los elementos en ambas subsecuencias sea igual. Cada número en la array debe pertenecer solo a una de las dos subsecuencias. Imprime todas las combinaciones posibles de dos subsecuencias.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 9, 4, 5}
Salida:
1 2 9 y 3 4 5
1 2 4 5 y 3 9
3 9 y 1 2 4 5
3 4 5 y 1 2 9Entrada: arr[] = {4, -1, 2, -1}
Salida:
4 -1 -1 y 2
2 y 4 -1 -1
Enfoque: una solución simple es formar todos los pares posibles de subsecuencias usando recursividad y comparar la suma de elementos en ambas subsecuencias. Para cada elemento de la array, tenemos dos opciones, podemos tomar el elemento actual en la primera subsecuencia o en la segunda.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
// Function to print the subsequence elements
void print(int g1[], int a, int g2[], int b)
{
// Prints elements of the 1st subarray
for (int i = 0; i < a; i++) {
cout << g1[i] << " ";
}
cout << "and ";
// Prints elements of the 2nd subarray
for (int i = 0; i < b; i++) {
cout << g2[i] << " ";
}
cout << endl;
}
// Function that returns true if the sum of the
// elements of arrays g1[] and g2[] is equal
bool checksum(int g1[], int a, int g2[], int b)
{
int i, x;
// Adding elements of the 1st array
for (i = 0, x = 0; i < a; i++) {
x += g1[i];
}
// Subtracting elements of the 2nd array
for (i = 0; i < b; i++) {
x -= g2[i];
}
// If x is 0 then the sum of elements
// in both the arrays is equal
return (x == 0);
}
// Function to find all valid subsequences
void formgroups(int arr[], int x, int g1[], int a,
int g2[], int b, int n)
{
// Base Case
if (x == n) {
// If sum of the two subsequences
// is equal then print the elements
if (checksum(g1, a, g2, b)) {
// Print the subsequences
print(g1, a, g2, b);
}
return;
}
// Recursive Case
// Choose current element to be a
// part of the first subsequence
g1[a] = arr[x];
formgroups(arr, x + 1, g1, a + 1, g2, b, n);
// Choose current element to be a
// part of the second subsequence
g2[b] = arr[x];
formgroups(arr, x + 1, g1, a, g2, b + 1, n);
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 9, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int g1[MAX], g2[MAX];
formgroups(arr, 0, g1, 0, g2, 0, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100000;
// Function to print the
// subsequence elements
static void print(int g1[], int a,
int g2[], int b)
{
// Prints elements of the 1st subarray
for (int i = 0; i < a; i++)
{
System.out.print(g1[i] + " ");
}
System.out.print("and ");
// Prints elements of the 2nd subarray
for (int i = 0; i < b; i++)
{
System.out.print(g2[i] + " ");
}
System.out.println();
}
// Function that returns true if
// the sum of the elements of
// arrays g1[] and g2[] is equal
static boolean checksum(int g1[], int a,
int g2[], int b)
{
int i, x;
// Adding elements of the 1st array
for (i = 0, x = 0; i < a; i++)
{
x += g1[i];
}
// Subtracting elements of
// the 2nd array
for (i = 0; i < b; i++)
{
x -= g2[i];
}
// If x is 0 then the sum of elements
// in both the arrays is equal
return (x == 0);
}
// Function to find all valid subsequences
static void formgroups(int arr[], int x,
int g1[], int a,
int g2[], int b, int n)
{
// Base Case
if (x == n)
{
// If sum of the two subsequences
// is equal then print the elements
if (checksum(g1, a, g2, b))
{
// Print the subsequences
print(g1, a, g2, b);
}
return;
}
// Recursive Case
// Choose current element to be a
// part of the first subsequence
g1[a] = arr[x];
formgroups(arr, x + 1, g1,
a + 1, g2, b, n);
// Choose current element to be a
// part of the second subsequence
g2[b] = arr[x];
formgroups(arr, x + 1, g1, a,
g2, b + 1, n);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 9, 4, 5 };
int n = arr.length;
int []g1 = new int[MAX];
int []g2 = new int[MAX];
formgroups(arr, 0, g1, 0, g2, 0, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 implementation of the approach
MAX = 100000
# Function to print the subsequence elements
def prints(g1, a, g2, b):
# Prints elements of the 1st subarray
for i in range(a):
print(g1[i], end = " ")
print("and ", end = "")
# Prints elements of the 2nd subarray
for i in range(b):
print(g2[i], end = " ")
print("\n", end = "")
# Function that returns true if the sum of the
# elements of arrays g1[] and g2[] is equal
def checksum(g1, a, g2, b):
# Adding elements of the 1st array
x = 0
for i in range(0, a, 1):
x += g1[i]
# Subtracting elements of the 2nd array
for i in range(b):
x -= g2[i]
# If x is 0 then the sum of elements
# in both the arrays is equal
return (x == 0)
# Function to find all valid subsequences
def formgroups(arr, x, g1, a, g2, b, n):
# Base Case
if (x == n):
# If sum of the two subsequences
# is equal then print the elements
if (checksum(g1, a, g2, b)):
# Print the subsequences
prints(g1, a, g2, b)
return
# Recursive Case
# Choose current element to be a
# part of the first subsequence
g1[a] = arr[x]
formgroups(arr, x + 1, g1, a + 1, g2, b, n)
# Choose current element to be a
# part of the second subsequence
g2[b] = arr[x]
formgroups(arr, x + 1, g1, a, g2, b + 1, n)
# Driver code
if __name__ == '__main__':
arr = [1, 2, 3, 9, 4, 5]
n = len(arr)
g1 = [0 for i in range(MAX)]
g2 = [0 for i in range(MAX)]
formgroups(arr, 0, g1, 0, g2, 0, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100000;
// Function to print the
// subsequence elements
static void print(int []g1, int a,
int []g2, int b)
{
// Prints elements of the 1st subarray
for (int i = 0; i < a; i++)
{
Console.Write(g1[i] + " ");
}
Console.Write("and ");
// Prints elements of the 2nd subarray
for (int i = 0; i < b; i++)
{
Console.Write(g2[i] + " ");
}
Console.WriteLine();
}
// Function that returns true if
// the sum of the elements of
// arrays g1[] and g2[] is equal
static bool checksum(int []g1, int a,
int []g2, int b)
{
int i, x;
// Adding elements of the 1st array
for (i = 0, x = 0; i < a; i++)
{
x += g1[i];
}
// Subtracting elements of
// the 2nd array
for (i = 0; i < b; i++)
{
x -= g2[i];
}
// If x is 0 then the sum of elements
// in both the arrays is equal
return (x == 0);
}
// Function to find all valid subsequences
static void formgroups(int []arr, int x,
int []g1, int a,
int []g2, int b, int n)
{
// Base Case
if (x == n)
{
// If sum of the two subsequences
// is equal then print the elements
if (checksum(g1, a, g2, b))
{
// Print the subsequences
print(g1, a, g2, b);
}
return;
}
// Recursive Case
// Choose current element to be a
// part of the first subsequence
g1[a] = arr[x];
formgroups(arr, x + 1, g1,
a + 1, g2, b, n);
// Choose current element to be a
// part of the second subsequence
g2[b] = arr[x];
formgroups(arr, x + 1, g1, a,
g2, b + 1, n);
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 3, 9, 4, 5 };
int n = arr.Length;
int []g1 = new int[MAX];
int []g2 = new int[MAX];
formgroups(arr, 0, g1, 0, g2, 0, n);
}
}
// This code is contributed by anuj_67...
PHP
<?php
// PHP implementation of the approach
const MAX = 100000;
// Function to print the subsequence elements
function printi($g1, $a, $g2, $b)
{
// Prints elements of the 1st subarray
for ($i = 0; $i < $a; $i++)
{
echo ($g1[$i]);
echo " ";
}
echo ("and ");
// Prints elements of the 2nd subarray
for ($i = 0; $i < $b; $i++)
{
echo ($g2[$i]);
echo " ";
}
echo "\n";
}
// Function that returns true if the sum of the
// elements of arrays g1[] and g2[] is equal
function checksum($g1, $a, $g2, $b)
{
// Adding elements of the 1st array
for ($i = 0, $x = 0; $i < $a; $i++)
{
$x += $g1[$i];
}
// Subtracting elements of the 2nd array
for ($i = 0; $i < $b; $i++)
{
$x -= $g2[$i];
}
// If x is 0 then the sum of elements
// in both the arrays is equal
return ($x == 0);
}
// Function to find all valid subsequences
function formgroups($arr, $x, $g1, $a,
$g2, $b, $n)
{
// Base Case
if ($x == $n)
{
// If sum of the two subsequences
// is equal then print the elements
if (checksum($g1, $a, $g2, $b))
{
// Print the subsequences
printi($g1, $a, $g2, $b);
}
return;
}
// Recursive Case
// Choose current element to be a
// part of the first subsequence
$g1[$a] = $arr[$x];
formgroups($arr, $x + 1, $g1,
$a + 1, $g2, $b, $n);
// Choose current element to be a
// part of the second subsequence
$g2[$b] = $arr[$x];
formgroups($arr, $x + 1, $g1, $a,
$g2, $b + 1, $n);
}
// Driver code
$arr = array(1, 2, 3, 9, 4, 5);
$n = count($arr);
$g1 = array();
$g2 = array();
formgroups($arr, 0, $g1, 0, $g2, 0, $n);
// This code is contributed by Naman_Garg.
?>
Javascript
<script>
// Javascript implementation of the approach
var MAX = 100000;
// Function to print the subsequence elements
function print(g1, a, g2, b)
{
// Prints elements of the 1st subarray
for(var i = 0; i < a; i++)
{
document.write( g1[i] + " ");
}
document.write("and ");
// Prints elements of the 2nd subarray
for(var i = 0; i < b; i++)
{
document.write( g2[i] + " ");
}
document.write("<br>");
}
// Function that returns true if the sum of the
// elements of arrays g1[] and g2[] is equal
function checksum(g1, a, g2, b)
{
var i, x;
// Adding elements of the 1st array
for(i = 0, x = 0; i < a; i++)
{
x += g1[i];
}
// Subtracting elements of the 2nd array
for(i = 0; i < b; i++)
{
x -= g2[i];
}
// If x is 0 then the sum of elements
// in both the arrays is equal
return (x == 0);
}
// Function to find all valid subsequences
function formgroups(arr, x, g1, a, g2, b, n)
{
// Base Case
if (x == n)
{
// If sum of the two subsequences
// is equal then print the elements
if (checksum(g1, a, g2, b))
{
// Print the subsequences
print(g1, a, g2, b);
}
return;
}
// Recursive Case
// Choose current element to be a
// part of the first subsequence
g1[a] = arr[x];
formgroups(arr, x + 1, g1, a + 1,
g2, b, n);
// Choose current element to be a
// part of the second subsequence
g2[b] = arr[x];
formgroups(arr, x + 1, g1, a, g2,
b + 1, n);
}
// Driver code
var arr = [ 1, 2, 3, 9, 4, 5 ];
var n = arr.length;
var g1 = Array(MAX).fill(0),
g2 = Array(MAX).fill(0);
formgroups(arr, 0, g1, 0, g2, 0, n);
// This code is contributed by noob2000
</script>
Producción:
1 2 9 and 3 4 5 1 2 4 5 and 3 9 3 9 and 1 2 4 5 3 4 5 and 1 2 9
Complejidad del tiempo: O(2 n )
Publicación traducida automáticamente
Artículo escrito por SuveenKumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA