C++ 不包含给定元素的等和数组分割

问题描述

对于一个索引和一个数组arr[]，检查数组arr[]是否可以分割成两个不相交的子集，排除arr[index]，使得两个子集的元素和相等。

示例 1

输入

arr[] = {4, 3, 1, 2}, Index = 1

输出

No

解释

我们必须排除arr [1] = 3

所有可能的集合为 −

Set 1: (4), Set 2: (2, 1), sum = 4≠3
Set 1: (4,1), Set 2: (2), sum = 5≠2
Set 1: (4,2), Set 2: (1), sum = 6≠1

没有任何组合满足条件。

示例 2

输入

arr[] = {2, 5, 1, 4, 0}, index = 4

输出

Yes
Set 1 : (2, 4), sum = 6
Set 2 : (5, 1), sum = 6

解决方案

这个问题是对分区问题的修改版本，并增加了一个限制：问题中给定的索引不能包含在数组的任一分区集合中。

首先，我们需要计算数组中除了给定索引处的值之外的所有元素的和。

只有当和为偶数时，才有可能将数组分为两个相等的部分。如果和为奇数，则没有可能的解决方案。如果和为偶数，我们将继续定义两个变量set1Sum和set2Sum来保存两个集合的和。

我们将使用递归来确定set1Sum和set2Sum是否相等。起始索引为0，并且数组将被递归地遍历。对于数组的每个索引，有两个选择，要么包含在set1Sum中，要么包含在set2Sum中。

我们将首先调用递归函数来将当前索引添加到set1中，然后添加到set2中。同时，请确保检查当前索引是否不是问题中给定的索引（必须排除的索引），如果等于该索引，则在不更新和的情况下调用下一个位置。一旦完整地遍历了整个数组，比较set1Sum和set2Sum。如果和相等，则返回，否则进行回溯并检查其他选项。

方法

步骤1 - 定义一个函数，命名为calcPartitionSum。它将接受6个参数，给定的数组arr，arr中的元素数量n，第一个集合的和set1Sum，第二个集合的和set2Sum，必须排除的元素的索引index和数组中的当前位置i。

步骤2 - 如果i达到arr的末尾，则该函数返回true，如果set1Sum等于set2Sum，则返回true，否则返回false。

步骤3 - 如果i达到了索引index，则函数将调用自身，并传递下一个i而不更新和。

步骤4 - 当i不等于index时，函数将首先为set1调用自身，然后为set2调用自身。在每个函数调用中，它将通过将arr[i]添加到相应集合的和中来更新和的值。

步骤5 - 定义另一个函数，命名为calcFullSum，用于计算整个数组的总和，不包括给定索引处的值。如果和为奇数，则该函数返回false，并调用calcPartitionSum。

步骤6 - 调用calcPartitionSum函数时，将参数set1Sum和set2Sum初始化为0，index设置为给定的索引，i设置为0。

步骤7 - calcPartitionSum的返回值将确定答案。

示例

以下是一个检查数组是否可以分为两个不相交的集合（排除arr[index]），使得两个集合的和相等的C++程序。

#include <bits/stdc++.h>
using namespace std;
// Function to divide the array into 2 sets and
// to check if the sum of sets becomes equal.
bool calcPartitionSum(int arr[], int n, int set1Sum, int set2Sum, int index, int i){
   // Compare the sums if i reaches the end of array
   // return true if both are equal else return false.
   if (i == n){
      return (set1Sum == set2Sum);
   }
   // If i reaches index, then the function calls
   // itself with the next i without updating the sums
   if (i == index){
      calcPartitionSum(arr, n, set1Sum, set2Sum, index, i + 1);
   }
   // Calling calcPartitionSum by including the value at
   // current index in the set 1
   bool updateSet1 = calcPartitionSum(arr, n, set1Sum + arr[i],set2Sum, index, i + 1);
   // Calling calcPartitionSum by including the value at
   // current index in the set 2
   bool updateSet2 = calcPartitionSum(arr, n, set1Sum, set2Sum + arr[i], index, i + 1);
   // returning true if any one of above calls give a true result
   return  updateSet1 || updateSet2;
}
// Function to check if the array can be divided into 2 sets
// and calls calcPartitionSum accordingly
bool calcFullSum(int arr[], int n, int index){
   // Initiate sum variable with 0
   int sum = 0;
   // Iterate through the whole array and update the sum
   for (int i = 0; i < n; i++) {
      // Not updating the value of sum for given index
      // that needs to be excluded
      if (i == index){
         continue;
      }
      sum += arr[i];
   }
   // If sum is odd return false
   if (sum % 2 != 0) return false;
   // If sum is even call calcPartitionSum function.
   // The parameters set1Sum, set2Sum and i are initiated as 0
   return calcPartitionSum(arr, n, 0, 0, index, 0);
}
// Driver Code
int main() {
   int arr[] = {2, 5, 1, 4, 0};
   int index = 4;
   int n = sizeof(arr) / sizeof(arr[0]);
   if (calcFullSum(arr, n, index)){ 
      cout << "Yes";
   }
   else{
      cout << "No";
   }
   return 0;
}

输出

给定的输入数组 arr[] = {2, 5, 1, 4, 0} 和索引 index = 4，上述的 C++ 程序将产生以下输出 –