原文:
给定数组 arr[]。确定是否可以将数组拆分为两组，使两组中的元素之和相等。如果可能，打印两套。如果不可能，则输出-1。
示例:
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.
我们已经在中讨论了一个pg电子试玩链接的解决方案，来看看数组是否可以分区。在这篇文章中，我们打印了两套也是打印的。我们传递两个向量 set1 和 set2 以及两个和变量 sum1 和 sum2。递归遍历数组。在每个数组位置都有两个选择:要么将当前元素添加到集合 1，要么添加到集合 2。递归调用这两个条件，并相应地更新向量 set1 和 set2。如果当前元素被添加到集合 1，那么将当前元素添加到 sum1，并将其插入向量集合 1。如果当前元素包含在集合 2 中，重复相同的步骤。在数组遍历结束时，比较两者的总和。如果两个和相等，则打印两个向量，否则回溯以检查其他可能性。
实施:
c
// cpp program to print equal sum two subsets of
// an array if it can be partitioned into subsets.
#include
using namespace std;
/// function to print the equal sum sets of the array.
void printsets(vector set1, vector 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& set1,
vector& 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 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 set1 = new arraylist();
static list set2 = new arraylist();
/// 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)
python 3
# 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 set1,
list 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 set1,
ref list 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 set1 = new list();
list set2 = new list();
/// 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)
服务器端编程语言（professional hypertext preprocessor 的缩写）
java 描述语言
输出:
5 5 1
11
时间复杂度:指数 o(2^n) 辅助空间: o(n)(不考虑函数调用栈的大小)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
