排除给定元素的相等和数组分区
问题陈述
对于索引和 arr[]。检查 array[] 是否可以划分为两个不相交的集合，排除 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 中。
我们将首先调用递归函数，将当前索引添加到集合 1 中，然后添加到集合 2 中。除此之外，还要确保检查当前索引是否不是问题中给出的索引(必须排除)，如果它等于该索引，则调用下一个位置而不更新总和。遍历完整个数组后，比较 theset1Sum 和 set2Sum。如果总和相等，则返回，否则回溯并检查其他选项。
方法
步骤 1 − 定义一个函数，我们将其命名为 calcPartitionSum。它将接受 6 个参数，一个给定的数组 (arr)、arr 中给定数量的元素 (n)、第一个集合的总和 (set1Sum)、第二个集合的总和 (set2Sum)、必须排除的元素的索引 (index) 以及数组中的当前位置 (i)。
步骤 2 - 如果 i 到达 arr 的末尾，则如果 set1Sum 等于 set2Sum，则函数返回 true，否则返回 false。
步骤 3 - 如果 i 到达索引，则函数使用下一个 i 调用自身而不更新总和。
步骤 4 - 每当 i 不等于索引时，函数将首先为 set1 调用自身，然后为 set 2 调用自身。在函数调用中，它将通过将 arr[i] 添加到相应集合的总和来更新 sum 的值。
步骤 5 - 定义另一个函数，我们将其命名为 calcFullSum，用于计算除给定索引处的值之外的整个数组的总和。如果总和为奇数，此函数将返回 false，并调用 calcPartitionSum。
步骤 6 - calcPartitionSum 函数调用将参数 set1Sum 和 set2Sum 初始化为 0，index 等于给定的索引，i 等于 0。
步骤 7 - calcPartitionSum 返回的值将决定答案。
示例
下面是一个 C++ 程序，用于检查 array[] 是否可以分成两个不相交的集合，不包括 arr[index]，使得两个集合的总和相等。
#include <bits/stdc++.h>
using namespace std;
// 函数将数组分成 2 个集合并
// 检查集合的总和是否相等。
bool calcPartitionSum(int arr[], int n, int set1Sum, int set2Sum, int index, int i){
// 如果 i 到达数组末尾，则比较总和
// 如果两者相等，则返回 true，否则返回 false。
if (i == n){
return (set1Sum == set2Sum);
}
// 如果 i 到达索引，则函数使用下一个 i 调用自身，而不更新总和
if (i == index){
calcPartitionSum(arr, n, set1Sum, set2Sum, index, i + 1);
}
// 通过将当前索引处的值包含在集合 1 中来调用 calcPartitionSum
bool updateSet1 = calcPartitionSum(arr, n, set1Sum + arr[i],set2Sum, index, i + 1);
// 通过将值包含在集合 2 中的当前索引处来调用 calcPartitionSum
bool updateSet2 = calcPartitionSum(arr, n, set1Sum, set2Sum + arr[i], index, i + 1);
// 如果上述任何一个调用给出 true 结果，则返回 true
return updateSet1 || updateSet2;
}
// 函数用于检查数组是否可以分为 2 个集合
// 并相应地调用 calcPartitionSum
bool calcFullSum(int arr[], int n, int index){
// 用 0 初始化 sum 变量
int sum = 0;
// 遍历整个数组并更新 sum
for (int i = 0; i < n; i++) {
// 不更新给定索引的 sum 值
// 需要排除
if (i == index){
continue;
}
sum += arr[i];
}
// 如果 sum 为奇数，则返回 false
if (sum % 2 != 0) return false;
// 如果 sum 为偶数，则调用 calcPartitionSum 函数。
// 参数 set1Sum、set2Sum 和 i 均以 0 为初始值
return calcPartitionSum(arr, n, 0, 0, index, 0);
}
// 驱动代码
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++ 程序将产生以下输出 −
Yes
时间复杂度
此算法的时间复杂度为 O(2^n)，其中 n 是数组中的元素数量。由于 calcPartitionSum 被调用两次，一次用于 set1Sum，一次用于 set2Sum，数组 T.C. 中的每个位置都变为 O(2^n)。
空间复杂度
此算法的空间复杂度为 O(n)，其中 n 是数组中的元素数量。由于 calcPartitionSum 是一个递归函数，因此它将具有大小为 n 的递归调用堆栈。
结论
因此，我们使用递归解决了排除给定元素的等和数组分区问题。我们首先检查将数组分成 2 个集合(不包括给定的索引)是否可以给出结果。如果可以将数组分成 2 个集合，我们将检查在划分数组后可以创建的 2 个集合的每种可能组合，如果其中任何一个组合满足给定的条件，则返回 true。
