資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
服裝學
法律用 C++ 分割相等的子集和
假設我們有一個只有正整數的非空陣列，我們必須找出陣列是否可以分成兩個子集，使得兩個子集中元素的和相等。因此，如果輸入類似於 [1,5,11,5]，則輸出將為真。因為該陣列可以分成 [1, 5, 5] 和 [11]
為了解決這個問題，我們將按照以下步驟操作 −
- n := 陣列大小
- sum := 0
- i := 0 到 n – 1
- sum := sum + nums[i]
- 如果和為奇，則返回假
- sum := sum / 2
- 建立一個大小為 sum + 1 的陣列 dp
- dp[0] := 真
- 對於 i 在 0 到 n – 1 之間取值
- x := nums[i]
- 對於 j 從 sum 到 j – x 取值
- dp[j] := dp[j] 或 dp[j - x]（不為 0）
- 返回 dp[sum]
示例（C++）
讓我們看以下實現以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
}輸入
[1,5,11,5]
輸出
1
更新時間： 28-4-2020
328 瀏覽量
廣告