数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学排除给定元素的等和数组划分
问题陈述
对于一个索引和一个数组 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 中。
我们将首先调用递归函数将当前索引添加到集合 1 中，然后添加到集合 2 中。同时，确保检查当前索引是否不是问题中给定的索引（必须排除），如果等于该索引，则在不更新总和的情况下调用下一个位置。一旦完整遍历数组，比较 set1Sum 和 set2Sum。如果总和相等，则返回；否则回溯并检查其他选项。
方法
步骤 1 - 定义一个函数，我们将其命名为 calcPartitionSum。它将接收 6 个参数：给定的数组 (arr)、arr 中给定的元素个数 (n)、第一个集合的和 (set1Sum)、第二个集合的和 (set2Sum)、要排除的元素的索引 (index) 和数组中的当前位置 (i)。
步骤 2 - 如果 i 达到 arr 的末尾，则如果 set1Sum 等于 set2Sum，则函数返回 true，否则返回 false。
步骤 3 - 如果 i 达到索引，则函数将自身与下一个 i 一起调用，而不更新总和。
步骤 4 - 当 i 不等于 index 时，函数将首先为 set1 调用自身，然后为 set 2 调用自身。在一个函数调用中，它将通过将 arr[i] 添加到相应集合的和来更新和的值。
步骤 5 - 定义另一个函数，我们将其命名为 calcFullSum，用于计算整个数组的和，但不包括给定索引处的数值。如果总和为奇数，则此函数将返回 false，并将调用 calcPartitionSum。
步骤 6 - calcPartitionSum 函数调用将具有初始化为 0 的 set1Sum 和 set2Sum 参数，index 等于给定的 index，i 等于 0。
步骤 7 - calcPartitionSum 返回的值将确定答案。
示例
下面是一个 C++ 程序，用于检查数组 arr[] 是否可以划分为两个不相交的集合，排除 arr[index]，使得两个集合的和相等。
#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++ 程序将产生以下输出：
Yes
时间复杂度
此算法的时间复杂度为 O(2^n)，其中 n 是数组中元素的数量。由于 calcPartitionSum 对于数组中的每个位置都被调用两次，一次用于 set1Sum，一次用于 set2Sum，因此时间复杂度变为 O(2^n)。
空间复杂度
此算法的空间复杂度为 O(n)，其中 n 是数组中元素的数量。由于 calcPartitionSum 是一个递归函数，它将具有大小为 n 的递归调用栈。
结论
因此，我们使用递归解决了排除给定元素的等和数组划分问题。我们首先检查是否可以将数组划分为 2 个集合（排除给定索引）并得到结果。如果可以将数组划分为 2 个集合，我们将检查划分数组后可以创建的 2 个集合的每种可能的组合，如果其中任何一种组合满足给定条件，则返回 true。
浏览量：107
