分區 主分區 和 擴展分區

Description:

描述：

This is a popular interview coding problem which has been featured in interview rounds of Amazon, Oyo rooms, Adobe.

這是一個受歡迎的采訪編碼問題，已在亞馬遜，Oyo房間，Adobe的采訪回合中出現。

Problem statement:

問題陳述：

Given a set of numbers, check whether it can be partitioned into two subsets or not such that the sum of elements in both subsets is same.

給定一組數字，請檢查是否可以將其劃分為兩個子集，以使兩個子集中的元素之和相同。

Input:

輸入：

First line contains N, the number of elements in the set and the second line contains the elements of the set.

第一行包含N ，集合中元素的數量，第二行包含該集合的元素。

Output:

輸出：

Print YES if the given set can be partitioned into two subsets such that the sum of elements in both subsets is equal, else print NO.

YES打印如果給定的集可被劃分成兩個子集，使得元件在兩個子集之和是相等的，否則打印NO。

Example with explanation:

帶有說明的示例：

    N=5
Elements are:
3, 4, 6, 2, 5
Output: Yes
The set can be partitioned into two subsets with equal sum,
Which is, 
subset1: {3, 2, 5} with sum 10
subset2: {4, 6} with sum 10
Another example can be,
N=6
Elements are;
1, 3, 4, 8, 5, 6
Output would be NO since there is no way to do so.

Solution Approach:

解決方法：

We would first check the recursive solution.

我們將首先檢查遞歸解決方案。

Let's create two subset initially where the first subset contains all the elements and the second one is an empty one.

首先創建兩個子集，其中第一個子集包含所有元素，第二個子集為空元素。

We calculate the total sum and our function is:

我們計算總和，我們的函數是：

    bool EqualPartition(index,subset1Sum,subset2Sum)

So, initially the function call will be

因此，最初的函數調用將是

    bool EqualPartition(n-1,total_sum,0)

Where n-1= index of last element, which is index

其中n-1 =最后一個元素的 索引 ，即索引

total_sum= total sum of all elements, which is subset1Sum

total_sum =所有元素的總和 ，即subset1Sum

0= subset2Sum initially

0 =子集2初始總和

Now, our idea is to check by either including the indexed element in subset2 or by not including. And we will continue doing this recursively until we reach our base case.

現在，我們的想法是通過將索引元素包括在subset2中或不包括進行檢查。 我們將繼續遞歸執行此操作，直到達到基本情況為止。

Let's see the function definition:

讓我們看一下函數定義：

Function
EqualPartition(index,subset1Sum,subset2Sum):
if subset1Sum==subset2Sum //our objective to find
return true
if index<0
return false
return  EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) || 
EqualPartition(index-1,subset1Sum,subset2Sum)
End Function

So the recursive definition consists of the case what we discussed above.

因此，遞歸定義由我們上面討論的情況組成。

    EqualPartition(index-1,subset1Sum-arr[index],subset2Sum+arr[index]) = add the current element(arr[index]) to subset2 
EqualPartition(index-1,subset1Sum,subset2Sum) = ignore the current element and recur for other elements

So this recursive definition will generate a recursion tree where we can find many overlapping sub problems, hence we would solve by dynamic programing. The solution approach is similar to subset problem.

因此，此遞歸定義將生成一個遞歸樹，在其中可以找到許多重疊的子問題，因此可以通過動態編程來解決。 解決方法類似于子集問題 。

So we have to create the DP table and fill up the table as per the solution approach in this article.

因此，我們必須根據本文中的解決方案方法創建DP表并填寫該表。

So, we have dp[n+1][sum+1] filled up now.

因此，我們現在已經填充了dp [n + 1] [sum + 1] 。

sum = total sum of elements

總和 =元素總和

How can we utilize this piece of information as our solution?

我們如何利用這些信息作為我們的解決方案？

Not too tough. If dp[i][sum/2] is true for i= 1 to n, it ensures that we have a subset which sums (sum/2) . Thus the remaining subset will have to be also of sum (sum/2).

不太難。 如果dp [i] [sum / 2]對于i = 1到n為true ，則確保我們有一個總和(sum / 2)的子集。 因此，剩余的子集也將必須是和(sum / 2) 。

This means we can have two equal sum subset.

這意味著我們可以有兩個相等的和子集。

Now, the point is what if (sum) is odd.

現在，關鍵是如果( sum )是奇數 。

Check our second example.

檢查我們的第二個例子。

Elements are: 1, 3, 4, 8, 5, 6
Sum=27 which is odd.
(sum/2)=13 with integer division.
dp[6][13] = true as 8,5 sums to 13.

元素是： 1、3、4、8、5、6
總和= 27 ，這很奇怪。
(sum / 2)= 13 (整數除法)。
dp [6] [13] = true，因為8,5等于13。

So we would get output YES but is it the solution?

因此，我們將輸出為YES，但這是解決方案嗎？

What's the catch then?

那有什么收獲呢？

The catch is if sum is odd, the answer will be always NO. You can't partition in two equal subsets.

問題是，如果總和是奇數 ，答案將始終為否 。 您不能分為兩個相等的子集。

So before doing anything, just check whether the total sum is odd or not. If the sum is odd simply return false else proceed with the further DP. This would optimize time too.

因此，在執行任何操作之前，只需檢查總和是否為奇數 。 如果總和是奇數，則簡單地返回false，否則繼續下一個DP。 這也會優化時間。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
bool equalsubset(vector<int> arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
//cout<<sum<<endl;
if (sum % 2 == 1)
return false;
bool dp[n + 1][sum + 1];
memset(dp, false, sizeof(dp));
for (int i = 0; i <= sum; i++)
dp[0][i] = false;
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
if (i >= arr[j - 1])
dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]];
else
dp[j][i] = dp[j - 1][i];
}
}
for (int i = 1; i <= n; i++)
if (dp[i][sum / 2])
return true;
return false;
}
int main()
{
int t, n, item;
cout << "Enter number of test cases: ";
cin >> t;
for (int i = 0; i < t; i++) {
cout << "Enter n, number of elements: ";
cin >> n;
vector<int> a;
cout << "Enter elements: ";
for (int j = 0; j < n; j++) {
cin >> item;
a.push_back(item);
}
if (equalsubset(a, n))
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}

Output

輸出量

Enter number of test cases: 2
Enter n, number of elements: 5
Enter elements: 3 4 6 2 5
YES
Enter n, number of elements: 6
Enter elements: 1 3 4 8 5 6
NO

翻譯自: https://www.includehelp.com/icp/equal-sum-partition.aspx

分區 主分區 和 擴展分區