資料結構
網路
關係資料庫管理系統 (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
