打印数组的等和集（分区问题）|集2-yiteyi-C++库

给定数组arr[]。确定是否可以将数组拆分为两个集合，使两个集合中的元素之和相等。如果可能，则打印两套。如果不可能，则输出-1。 例如：

null

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 : -1No partitioning results in equal sum sets.

建议：请先在IDE上尝试您的方法，然后再查看解决方案。

先决条件： 划分问题 方法： 在以前的 post，一个使用递归本文对此进行了讨论。在这篇文章中，一个使用动态规划这是解释。我们的想法是声明两个集合：集合1和集合2。要恢复解决方案，从最终结果dp[n][k]开始向后遍历布尔dp表，其中n=元素数，k=总和/2。集合1将由有助于求和k的元素组成，其他不起作用的元素添加到集合2中。在每个位置执行以下步骤以恢复解决方案。

检查dp[i-1][sum]是否为真。如果为true，则当前元素不参与求和k。将此元素添加到集合2。用i-1更新索引i，总和保持不变。
如果dp[i-1][sum]为false，则当前元素对sum k起作用。将当前元素添加到集合1中。按i-1更新索引i，并按求和arr[i-1]进行求和。

重复上述步骤，直到遍历每个索引位置。 实施：

C++

                         // CPP program to print equal sum sets of array.                       
                         #include <bits/stdc++.h>                       
                         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<                                     int                                     > set1, set2;                       
           
                                                 // If partition is not possible print                       
                                                 // -1 and return.                       
                                                 if                                     (!dp[n][k]) {                       
                                                 cout <<                                     "-1"                                     ;                       
                                                 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 <<                                     "Set 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<Integer> set1 =                                     new                                     ArrayList<Integer>();                       
                                                 List<Integer> set2 =                                     new                                     ArrayList<Integer>();                       
                                   
                                                 // If partition is not possible                       
                                                 // print -1 and return.                       
                                                 if                                     (!dp[n][k])                       
                                                 {                       
                                                 System.out.print(                                     "-1"                                     );                       
                                                 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(                                     "Set 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)                       

Python3

                         # 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                                     (                                     "Set 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<                                     int                                     > set1 =                                     new                                     List<                                     int                                     >();                       
                                                 List<                                     int                                     > set2 =                                     new                                     List<                                     int                                     >();                       
                                   
                                                 // If partition is not possible                       
                                                 // print -1 and return.                       
                                                 if                                     (!dp[n, k])                       
                                                 {                       
                                                 Console.Write(                                     "-1"                                     );                       
                                                 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(                                     "Set 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)                       

Javascript

                         <script>                       
           
           
                         // Javascript program to print equal sum sets of array.                       
           
                         // Function to print equal sum                       
                         // sets of array.                       
                         function                                     printEqualSumSets(arr, n)                       
                         {                       
                                                 var                                     i, currSum;                       
                                   
                                                 // Finding sum of array elements                       
                                                 var                                     sum = 0;                       
                                   
                                                 for                                     (                                     var                                     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) {                       
                                                 document.write(                                     "-1"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Divide sum by 2 to find                       
                                                 // sum of two possible subsets.                       
                                                 var                                     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.                       
                                                 var                                     dp = Array.from(Array(n+1), ()=> Array(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.                       
                                                 var                                     set1 = [], set2=[];                       
           
                                                 // If partition is not possible print                       
                                                 // -1 and return.                       
                                                 if                                     (!dp[n][k]) {                       
                                                 document.write(                                     "-1<br>"                                     );                       
                                                 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(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(arr[i]);                       
                                                 }                       
                                                 }                       
           
                                                 // Print elements of both the sets.                       
                                                 document.write(                                     "Set 1 elements: "                                     );                       
                                                 for                                     (i = 0; i < set1.length; i++)                       
                                                 document.write( set1[i] +                                     " "                                     );                       
                                                 document.write(                                     "<br>Set 2 elements: "                                     );                       
                                                 for                                     (i = 0; i < set2.length; i++)                       
                                                 document.write( set2[i] +                                     " "                                     );                       
                         }                       
           
                         // Driver program.                       
                         var                                     arr = [ 5, 5, 1, 11 ];                       
                         var                                     n = arr.length;                       
                         printEqualSumSets(arr, n);                       
           
           
                         </script>                       

输出：

Set 1 elements: 1 5 5 Set 2 elements: 11

时间复杂性： O（n*k），其中k=sum（arr）/2 辅助空间： O（n*k）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章