原文:
给定数组 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.
先决条件: t5】方法:在帖子中，讨论了使用的pg电子试玩链接的解决方案。在这篇文章中，解释了一个使用的pg电子试玩链接的解决方案。 思路是声明两个集合集 1 和集 2。要恢复pg电子试玩链接的解决方案，请从最终结果 dp[n][k]开始向后遍历布尔 dp 表，其中 n =元素数量，k = sum/2。集合 1 将由对总和 k 有贡献的元素组成，其他没有贡献的元素被添加到集合 2。在每个位置遵循这些步骤来恢复pg电子试玩链接的解决方案。
-
检查 dp[i-1][sum]是否正确。如果为真，则当前元素对总和 k 没有贡献。将此元素添加到集合 2。用 i-1 更新指数 i，总和保持不变。
-
如果 dp[i-1][sum]为假，则当前元素贡献 sum k。将当前元素添加到集合 1。用 i-1 和 sum-arr[i-1]更新索引 i。
重复以上步骤，直到遍历每个索引位置。 执行:
c
// cpp program to print equal sum sets of array.
#include
using namespace std;
// function to print equal sum
// sets of array.
void printequalsumsets(int arr[], int n)
{
int i, currsum;
// finding sum of array elements
int sum = accumulate(arr, arr n, 0);
// check sum is even or odd. if odd
// then array cannot be partitioned.
// print -1 and return.
if (sum & 1) {
cout << "-1";
return;
}
// divide sum by 2 to find
// sum of two possible subsets.
int k = sum >> 1;
// boolean dp table to store result
// of states.
// dp[i][j] = true if there is a
// subset of elements in first i elements
// of array that has sum equal to j.
bool dp[n 1][k 1];
// if number of elements are zero, then
// no sum can be obtained.
for (i = 1; i <= k; i )
dp[0][i] = false;
// sum 0 can be obtained by not selecting
// any element.
for (i = 0; i <= n; i )
dp[i][0] = true;
// fill the dp table in bottom up manner.
for (i = 1; i <= n; i ) {
for (currsum = 1; currsum <= k; currsum ) {
// excluding current element.
dp[i][currsum] = dp[i - 1][currsum];
// including current element
if (arr[i - 1] <= currsum)
dp[i][currsum] = dp[i][currsum] |
dp[i - 1][currsum - arr[i - 1]];
}
}
// required sets set1 and set2.
vector set1, set2;
// if partition is not possible print
// -1 and return.
if (!dp[n][k]) {
cout << "-1\n";
return;
}
// start from last element in dp table.
i = n;
currsum = k;
while (i > 0 && currsum >= 0) {
// if current element does not
// contribute to k, then it belongs
// to set 2.
if (dp[i - 1][currsum]) {
i--;
set2.push_back(arr[i]);
}
// if current element contribute
// to k then it belongs to set 1.
else if (dp[i - 1][currsum - arr[i - 1]]) {
i--;
currsum -= arr[i];
set1.push_back(arr[i]);
}
}
// print elements of both the sets.
cout << "set 1 elements: ";
for (i = 0; i < set1.size(); i )
cout << set1[i] << " ";
cout << "\nset 2 elements: ";
for (i = 0; i < set2.size(); i )
cout << set2[i] << " ";
}
// driver program.
int main()
{
int arr[] = { 5, 5, 1, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
printequalsumsets(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print
// equal sum sets of array.
import java.io.*;
import java.util.*;
class gfg
{
// function to print equal
// sum sets of array.
static void printequalsumsets(int []arr,
int n)
{
int i, currsum, sum = 0;
// finding sum of array elements
for (i = 0; i < arr.length; i )
sum = arr[i];
// check sum is even or odd.
// if odd then array cannot
// be partitioned. print -1
// and return.
if ((sum & 1) == 1)
{
system.out.print("-1");
return;
}
// divide sum by 2 to find
// sum of two possible subsets.
int k = sum >> 1;
// boolean dp table to store
// result of states.
// dp[i,j] = true if there is a
// subset of elements in first i
// elements of array that has sum
// equal to j.
boolean [][]dp = new boolean[n 1][k 1];
// if number of elements are zero,
// then no sum can be obtained.
for (i = 1; i <= k; i )
dp[0][i] = false;
// sum 0 can be obtained by
// not selecting any element.
for (i = 0; i <= n; i )
dp[i][0] = true;
// fill the dp table
// in bottom up manner.
for (i = 1; i <= n; i )
{
for (currsum = 1;
currsum <= k;
currsum )
{
// excluding current element.
dp[i][currsum] = dp[i - 1][currsum];
// including current element
if (arr[i - 1] <= currsum)
dp[i][currsum] = dp[i][currsum] |
dp[i - 1][currsum - arr[i - 1]];
}
}
// required sets set1 and set2.
list set1 = new arraylist();
list set2 = new arraylist();
// if partition is not possible
// print -1 and return.
if (!dp[n][k])
{
system.out.print("-1\n");
return;
}
// start from last
// element in dp table.
i = n;
currsum = k;
while (i > 0 && currsum >= 0)
{
// if current element does
// not contribute to k, then
// it belongs to set 2.
if (dp[i - 1][currsum])
{
i--;
set2.add(arr[i]);
}
// if current element contribute
// to k then it belongs to set 1.
else if (dp[i - 1][currsum - arr[i - 1]])
{
i--;
currsum -= arr[i];
set1.add(arr[i]);
}
}
// print elements of both the sets.
system.out.print("set 1 elements: ");
for (i = 0; i < set1.size(); i )
system.out.print(set1.get(i) " ");
system.out.print("\nset 2 elements: ");
for (i = 0; i < set2.size(); i )
system.out.print(set2.get(i) " ");
}
// driver code
public static void main(string args[])
{
int []arr = new int[]{ 5, 5, 1, 11 };
int n = arr.length;
printequalsumsets(arr, n);
}
}
// this code is contributed by
// manish shaw(manishshaw1)
python 3
# python3 program to print equal sum
# sets of array.
import numpy as np
# function to print equal sum
# sets of array.
def printequalsumsets(arr, n) :
# finding sum of array elements
sum_array = sum(arr)
# check sum is even or odd. if odd
# then array cannot be partitioned.
# print -1 and return.
if (sum_array & 1) :
print("-1")
return
# divide sum by 2 to find
# sum of two possible subsets.
k = sum_array >> 1
# boolean dp table to store result
# of states.
# dp[i][j] = true if there is a
# subset of elements in first i elements
# of array that has sum equal to j.
dp = np.zeros((n 1, k 1))
# if number of elements are zero, then
# no sum can be obtained.
for i in range(1, k 1) :
dp[0][i] = false
# sum 0 can be obtained by not
# selecting any element.
for i in range(n 1) :
dp[i][0] = true
# fill the dp table in bottom up manner.
for i in range(1, n 1) :
for currsum in range(1, k 1) :
# excluding current element.
dp[i][currsum] = dp[i - 1][currsum]
# including current element
if (arr[i - 1] <= currsum) :
dp[i][currsum] = (dp[i][currsum] or
dp[i - 1][currsum - arr[i - 1]])
# required sets set1 and set2.
set1, set2 = [], []
# if partition is not possible print
# -1 and return.
if ( not dp[n][k]) :
print("-1")
return
# start from last element in dp table.
i = n
currsum = k
while (i > 0 and currsum >= 0) :
# if current element does not
# contribute to k, then it belongs
# to set 2.
if (dp[i - 1][currsum]) :
i -= 1
set2.append(arr[i])
# if current element contribute
# to k then it belongs to set 1.
elif (dp[i - 1][currsum - arr[i - 1]]) :
i -= 1
currsum -= arr[i]
set1.append(arr[i])
# print elements of both the sets.
print("set 1 elements:", end = " ")
for i in range(len(set1)) :
print(set1[i], end = " ")
print("\nset 2 elements:", end = " ")
for i in range(len(set2)) :
print(set2[i], end = " ")
# driver code
if __name__ == "__main__" :
arr = [ 5, 5, 1, 11 ]
n = len(arr)
printequalsumsets(arr, n)
# this code is contributed by ryuga
c
// c# program to print
// equal sum sets of array.
using system;
using system.linq;
using system.collections.generic;
class gfg
{
// function to print equal
// sum sets of array.
static void printequalsumsets(int []arr,
int n)
{
int i, currsum, sum = 0;
// finding sum of array elements
for (i = 0; i < arr.length; i )
sum = arr[i];
// check sum is even or odd.
// if odd then array cannot
// be partitioned. print -1
// and return.
if ((sum & 1) == 1)
{
console.write("-1");
return;
}
// divide sum by 2 to find
// sum of two possible subsets.
int k = sum >> 1;
// boolean dp table to store
// result of states.
// dp[i,j] = true if there is a
// subset of elements in first i
// elements of array that has sum
// equal to j.
bool [,]dp = new bool[n 1, k 1];
// if number of elements are zero,
// then no sum can be obtained.
for (i = 1; i <= k; i )
dp[0, i] = false;
// sum 0 can be obtained by
// not selecting any element.
for (i = 0; i <= n; i )
dp[i, 0] = true;
// fill the dp table
// in bottom up manner.
for (i = 1; i <= n; i )
{
for (currsum = 1; currsum <= k; currsum )
{
// excluding current element.
dp[i, currsum] = dp[i - 1, currsum];
// including current element
if (arr[i - 1] <= currsum)
dp[i, currsum] = dp[i, currsum] |
dp[i - 1, currsum - arr[i - 1]];
}
}
// required sets set1 and set2.
list set1 = new list();
list set2 = new list();
// if partition is not possible
// print -1 and return.
if (!dp[n, k])
{
console.write("-1\n");
return;
}
// start from last
// element in dp table.
i = n;
currsum = k;
while (i > 0 && currsum >= 0)
{
// if current element does
// not contribute to k, then
// it belongs to set 2.
if (dp[i - 1, currsum])
{
i--;
set2.add(arr[i]);
}
// if current element contribute
// to k then it belongs to set 1.
else if (dp[i - 1, currsum - arr[i - 1]])
{
i--;
currsum -= arr[i];
set1.add(arr[i]);
}
}
// print elements of both the sets.
console.write("set 1 elements: ");
for (i = 0; i < set1.count; i )
console.write(set1[i] " ");
console.write("\nset 2 elements: ");
for (i = 0; i < set2.count; i )
console.write(set2[i] " ");
}
// driver code.
static void main()
{
int []arr = { 5, 5, 1, 11 };
int n = arr.length;
printequalsumsets(arr, n);
}
}
// this cide is contributed by
// manish shaw(manishshaw1)
java 描述语言
output :
set 1 elements: 1 5 5
set 2 elements: 11
时间复杂度: o(nk)，其中 k =和(arr) / 2 辅助空间: o(nk)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
