Dada una array arr[]. Determine si es posible dividir la array en dos conjuntos de manera que la suma de los elementos en ambos conjuntos sea igual. Si es posible, imprima ambos juegos. Si no es posible, emita -1.
Ejemplos:
Input : arr = {5, 5, 1, 11}
Output : Set 1 = {5, 5, 1},
Set 2 = {11}
Sum of both the sets is 11 and equal.
Input : arr = {1, 5, 3}
Output : -1
No partitioning results in equal sum sets.
Ya hemos discutido una solución en Problema de partición para encontrar si la array se puede particionar o no. En este post, imprimimos dos juegos que también están impresos. Publicamos pasar dos vectores set1 y set2 y dos variables de suma sum1 y sum2. Atraviesa la array recursivamente. En cada posición de la array hay dos opciones: agregar el elemento actual al conjunto 1 o al conjunto 2. Invoque recursivamente ambas condiciones y actualice los vectores conjunto1 y conjunto2 en consecuencia. Si el elemento actual se agrega al conjunto 1, agregue el elemento actual a sum1 e insértelo en el conjunto de vectores 1. Repita lo mismo si el elemento actual se incluye en el conjunto 2. Al final del recorrido de la array, compare ambas sumas. Si ambas sumas son iguales, imprima ambos vectores; de lo contrario, retroceda para verificar otras posibilidades.
Implementación:
C++
// CPP program to print equal sum two subsets of
// an array if it can be partitioned into subsets.
#include <bits/stdc++.h>
using namespace std;
/// Function to print the equal sum sets of the array.
void printSets(vector<int> set1, vector<int> set2)
{
int i;
/// Print set 1.
for (i = 0; i < set1.size(); i++) {
cout << set1[i] << " ";
}
cout << "\n";
/// Print set 2.
for (i = 0; i < set2.size(); i++) {
cout << set2[i] << " ";
}
}
/// Utility function to find the sets of the array which
/// have equal sum.
bool findSets(int arr[], int n, vector<int>& set1,
vector<int>& set2, int sum1, int sum2,
int pos)
{
/// If entire array is traversed, compare both the sums.
if (pos == n) {
/// If sums are equal print both sets and return
/// true to show sets are found.
if (sum1 == sum2) {
printSets(set1, set2);
return true;
}
/// If sums are not equal then return sets are not
/// found.
else
return false;
}
/// Add current element to set 1.
set1.push_back(arr[pos]);
/// Recursive call after adding current element to
/// set 1.
bool res = findSets(arr, n, set1, set2, sum1 + arr[pos],
sum2, pos + 1);
/// If this inclusion results in equal sum sets
/// partition then return true to show desired sets are
/// found.
if (res)
return res;
/// If not then backtrack by removing current element
/// from set1 and include it in set 2.
set1.pop_back();
set2.push_back(arr[pos]);
/// Recursive call after including current element to
/// set 2.
res = findSets(arr, n, set1, set2, sum1,
sum2 + arr[pos], pos + 1);
if (res == false)
if (!set2.empty())
set2.pop_back();
return res;
}
/// Return true if array arr can be partitioned
/// into two equal sum sets or not.
bool isPartitionPoss(int arr[], int n)
{
/// Calculate sum of elements in array.
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
/// If sum is odd then array cannot be
/// partitioned.
if (sum % 2 != 0)
return false;
/// Declare vectors to store both the sets.
vector<int> set1, set2;
/// Find both the sets.
return findSets(arr, n, set1, set2, 0, 0, 0);
}
// Driver code
int main()
{
int arr[] = { 5, 5, 1, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
if (!isPartitionPoss(arr, n)) {
cout << "-1";
}
return 0;
}
Java
// Java program to print equal sum two subsets
// of an array if it can be partitioned into
// subsets.
import java.io.*;
import java.util.*;
public class GFG {
// Declare Lists to store both
// the sets.
static List<Integer> set1 = new ArrayList<Integer>();
static List<Integer> set2 = new ArrayList<Integer>();
/// Function to print the equal sum sets
// of the array.
static void printSets()
{
int i;
/// Print set 1.
for (i = 0; i < set1.size(); i++) {
System.out.print(set1.get(i) + " ");
}
System.out.println();
/// Print set 2.
for (i = 0; i < set2.size(); i++) {
System.out.print(set2.get(i) + " ");
}
}
// Utility function to find the sets
// of the array which have equal sum.
static boolean findSets(Integer[] arr, int n,
int sum1, int sum2,
int pos)
{
// If entire array is traversed,
// compare both the sums.
if (pos == n) {
// If sums are equal print
// both sets and return true
// to show sets are found.
if (sum1 == sum2) {
printSets();
return true;
}
// If sums are not equal
// then return sets are not
// found.
else
return false;
}
// Add current element to set 1.
set1.add(arr[pos]);
// Recursive call after adding
// current element to set 1.
boolean res = findSets(arr, n, sum1 + arr[pos],
sum2, pos + 1);
// If this inclusion results in
// equal sum sets partition then
// return true to show desired
// sets are found.
if (res == true)
return res;
// If not then backtrack by removing
// current element from set1 and
// include it in set 2.
set1.remove(set1.size() - 1);
set2.add(arr[pos]);
// Recursive call after including
// current element to set 2.
res = findSets(arr, n, sum1, sum2
+ arr[pos],
pos + 1);
if (res == false)
if (set2.size() > 0)
set2.remove(set2.size() - 1);
return res;
}
// Return true if array arr can be
// partitioned into two equal sum
// sets or not.
static boolean isPartitionPoss(Integer[] arr,
int n)
{
// Calculate sum of elements in
// array.
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// If sum is odd then array cannot
// be partitioned.
if (sum % 2 != 0)
return false;
/// Find both the sets.
return findSets(arr, n, 0, 0, 0);
}
// Driver code
public static void main(String args[])
{
Integer[] arr = { 5, 5, 1, 11 };
int n = arr.length;
if (isPartitionPoss(arr, n) == false) {
System.out.print("-1");
}
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 program to print equal sum two subsets of
# an array if it can be partitioned into subsets.
# Function to print the equal sum sets of the array.
def printSets(set1, set2) :
# Print set 1.
for i in range(0, len(set1)) :
print ("{} ".format(set1[i]), end ="");
print ("")
# Print set 2.
for i in range(0, len(set2)) :
print ("{} ".format(set2[i]), end ="");
print ("")
# Utility function to find the sets of the
# array which have equal sum.
def findSets(arr, n, set1, set2, sum1, sum2, pos) :
# If entire array is traversed, compare both
# the sums.
if (pos == n) :
# If sums are equal print both sets and
# return true to show sets are found.
if (sum1 == sum2) :
printSets(set1, set2)
return True
# If sums are not equal then return
# sets are not found.
else :
return False
# Add current element to set 1.
set1.append(arr[pos])
# Recursive call after adding current
# element to set 1.
res = findSets(arr, n, set1, set2,
sum1 + arr[pos], sum2, pos + 1)
# If this inclusion results in an equal sum
# sets partition then return true to show
# desired sets are found.
if (res) :
return res
# If not then backtrack by removing current
# element from set1 and include it in set 2.
set1.pop()
set2.append(arr[pos])
# Recursive call after including current
# element to set 2 and removing the element
# from set 2 if it returns False
res= findSets(arr, n, set1, set2, sum1,
sum2 + arr[pos], pos + 1)
if not res:
set2.pop()
return res
# Return true if array arr can be partitioned
# into two equal sum sets or not.
def isPartitionPoss(arr, n) :
# Calculate sum of elements in array.
sum = 0
for i in range(0, n):
sum += arr[i]
# If sum is odd then array cannot be
# partitioned.
if (sum % 2 != 0) :
return False
# Declare vectors to store both the sets.
set1 = []
set2 = []
# Find both the sets.
return findSets(arr, n, set1, set2, 0, 0, 0)
# Driver code
arr = [5, 5, 1, 11]
n = len(arr)
if (isPartitionPoss(arr, n) == False) :
print ("-1")
# This code is contributed by Manish Shaw
# (manishshaw1)
C#
// C# program to print equal sum two subsets
// of an array if it can be partitioned into
// subsets.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class GFG {
/// Function to print the equal sum sets
// of the array.
static void printSets(List<int> set1,
List<int> set2)
{
int i;
/// Print set 1.
for (i = 0; i < set1.Count; i++) {
Console.Write(set1[i] + " ");
}
Console.WriteLine();
/// Print set 2.
for (i = 0; i < set2.Count; i++) {
Console.Write(set2[i] + " ");
}
}
// Utility function to find the sets
// of the array which have equal sum.
static bool findSets(int[] arr, int n,
ref List<int> set1,
ref List<int> set2,
int sum1, int sum2,
int pos)
{
// If entire array is traversed,
// compare both the sums.
if (pos == n) {
// If sums are equal print
// both sets and return true
// to show sets are found.
if (sum1 == sum2) {
printSets(set1, set2);
return true;
}
// If sums are not equal
// then return sets are not
// found.
else
return false;
}
// Add current element to set 1.
set1.Add(arr[pos]);
// Recursive call after adding
// current element to set 1.
bool res = findSets(arr, n, ref set1,
ref set2, sum1 + arr[pos],
sum2, pos + 1);
// If this inclusion results in
// equal sum sets partition then
// return true to show desired
// sets are found.
if (res == true)
return res;
// If not then backtrack by removing
// current element from set1 and
// include it in set 2.
set1.RemoveAt(set1.Count - 1);
set2.Add(arr[pos]);
// Recursive call after including
// current element to set 2.
res = findSets(arr, n, ref set1,
ref set2, sum1, sum2
+ arr[pos],
pos + 1);
if (res == false)
if (set2.Count > 0)
set2.RemoveAt(set2.Count - 1);
return res;
}
// Return true if array arr can be
// partitioned into two equal sum
// sets or not.
static bool isPartitionPoss(int[] arr,
int n)
{
// Calculate sum of elements in
// array.
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// If sum is odd then array cannot
// be partitioned.
if (sum % 2 != 0)
return false;
// Declare Lists to store both
// the sets.
List<int> set1 = new List<int>();
List<int> set2 = new List<int>();
/// Find both the sets.
return findSets(arr, n, ref set1,
ref set2, 0, 0, 0);
}
// Driver code
public static void Main()
{
int[] arr = { 5, 5, 1, 11 };
int n = arr.Length;
if (isPartitionPoss(arr, n) == false) {
Console.Write("-1");
}
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to print equal sum
// two subsets of an array if it
// can be partitioned into subsets.
// Function to print the equal
// sum sets of the array.
function printSets($set1, $set2)
{
$i = 0;
// Print set 1.
for ($i = 0; $i < count($set1); $i++)
{
echo ($set1[$i]." ");
}
echo ("\n");
// Print set 2.
for ($i = 0; $i < count($set2); $i++)
{
echo ($set2[$i]." ");
}
}
// Utility function to find the
// sets of the array which have
// equal sum.
function findSets($arr, $n, &$set1,
&$set2, $sum1,
$sum2, $pos)
{
// If entire array is traversed,
// compare both the sums.
if ($pos == $n)
{
// If sums are equal print
// both sets and return
// true to show sets are found.
if ($sum1 == $sum2)
{
printSets($set1, $set2);
return true;
}
// If sums are not equal then
// return sets are not found.
else
return false;
}
// Add current element to set 1.
array_push($set1, $arr[$pos]);
// Recursive call after adding
// current element to set 1.
$res = findSets($arr, $n, $set1, $set2,
$sum1 + $arr[$pos],
$sum2, $pos + 1);
// If this inclusion results in
// equal sum sets partition then
// return true to show desired
// sets are found.
if ($res)
return $res;
// If not then backtrack by
// removing current element
// from set1 and include it
// in set 2.
array_pop($set1);
array_push($set2, $arr[$pos]);
// Recursive call after including
// current element to set 2.
return findSets($arr, $n, $set1, $set2,
$sum1, $sum2 + $arr[$pos],
$pos + 1);
}
// Return true if array arr
// can be partitioned into
// two equal sum sets or not.
function isPartitionPoss($arr, $n)
{
// Calculate sum of
// elements in array.
$sum = 0;
for ($i = 0; $i < $n; $i++)
$sum += $arr[$i];
// If sum is odd then array
// cannot be partitioned.
if ($sum % 2 != 0)
return false;
// Declare vectors to
// store both the sets.
$set1 = array();
$set2 = array();
// Find both the sets.
return findSets($arr, $n, $set1,
$set2, 0, 0, 0);
}
// Driver code
$arr= array( 5, 5, 1, 11 );
$n = count($arr);
if (isPartitionPoss($arr, $n) == false)
echo ("-1");
// This code is contributed by
// Manish Shaw (manishshaw1)
?>
Javascript
<script>
// Javascript program to print equal sum two
// subsets of an array if it can be partitioned
// into subsets.
// Function to print the equal sum
// sets of the array.
function printSets(set1, set2)
{
var i;
// Print set 1.
for(i = 0; i < set1.length; i++)
{
document.write( set1[i] + " ");
}
document.write("<br>");
// Print set 2.
for(i = 0; i < set2.length; i++)
{
document.write( set2[i] + " ");
}
}
// Utility function to find the sets of the
// array which have equal sum.
function findSets(arr, n, set1, set2,
sum1, sum2, pos)
{
// If entire array is traversed,
// compare both the sums.
if (pos == n)
{
// If sums are equal print both sets
// and return true to show sets are found.
if (sum1 == sum2)
{
printSets(set1, set2);
return true;
}
// If sums are not equal then
// return sets are not found.
else
return false;
}
// Add current element to set 1.
set1.push(arr[pos]);
// Recursive call after adding current
// element to set 1.
var res = findSets(arr, n, set1, set2,
sum1 + arr[pos],
sum2, pos + 1);
// If this inclusion results in equal sum
// sets partition then return true to show
// desired sets are found.
if (res)
return res;
// If not then backtrack by removing
// current element from set1 and
// include it in set 2.
set1.pop();
set2.push(arr[pos]);
// Recursive call after including
// current element to set 2.
res = findSets(arr, n, set1, set2,
sum1, sum2 + arr[pos],
pos + 1);
if (res == false)
if (!set2.length == 0)
set2.pop();
return res;
}
// Return true if array arr can be partitioned
// into two equal sum sets or not.
function isPartitionPoss(arr, n)
{
// Calculate sum of elements in array.
var sum = 0;
for(var i = 0; i < n; i++)
sum += arr[i];
// If sum is odd then array cannot be
// partitioned.
if (sum % 2 != 0)
return false;
// Declare vectors to store both the sets.
var set1 = [];
var set2 = [];
// Find both the sets.
return findSets(arr, n, set1, set2, 0, 0, 0);
}
// Driver code
var arr = [ 5, 5, 1, 11 ];
var n = arr.length;
if (!isPartitionPoss(arr, n))
{
document.write( "-1");
}
// This code is contributed by SoumikMondal
</script>
Producción:
5 5 1 11
Complejidad de tiempo: Exponencial O(2^n)
Espacio auxiliar: O(n) (Sin considerar el tamaño de la pila de llamadas de función)
Imprima conjuntos de sumas iguales de arrays (problema de partición) | conjunto 2