数据结构
网络
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 浏览量
广告