题目描述：
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
数据范围：
$1\le nums.len \le 200; 1\le nums[i] \le 100$
题解：
总和为 sum，使用一个大小为 $\frac{sum}{2}$ 的背包装数字，最后返回装的价值是否等于容量。
也可以使用 $dp[i][j]$ 表示前 $i$ 个是否能够得到 $j$ 。初始时为 $dp[0][0] = 1, dp[0][j] = 0$ ， $dp[i][j] = dp[i-1][j] | dp[i-1][j - nums[i]]$ 。一维为 $dp[j] |= dp[i - nums[i]]$
还有更高级的做法，使用 bitset。因为使用一维dp时，需要从后往前遍历，相当于对 $dp[j\cdots size] |= dp[0\cdots size-j]$ 。使用移位可以表示为 $dp |= dp << nums[i]$ 。相当于对 $dp[0,j-1]$ 或上了 $0$ ，对后面的或上了 $dp[j-nums[i]]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int backet(vector<int> nums, int size)
{
int n = nums.size();
vector<int> dp(size + 1, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= size; j++)
{
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[size];
}
bool canPartition(vector<int> &nums)
{
int sum = 0;
for (auto &x : nums)
sum += x;
if (sum & 1)
return false;
if (backet(nums, sum / 2) == sum / 2)
return true;
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0, maxx = 0;
for(auto& x: nums) {sum += x; maxx = max(maxx, x);}
if(sum & 1 || maxx > sum / 2) return false;
int size = sum / 2;
vector<bool> dp(size + 1, false);
dp[0] = true;
for(int i = 0; i < n; ++i)
{
for(int j = size; j >= nums[i]; --j)
{
dp[j] = dp[j] | dp[j - nums[i]];
}
}
return dp[size];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int &num:nums) sum+=num;
if(sum&1) return false;
sum >>= 1;
bitset<10001> f; f[0]=1;
for(int i=0;i<nums.size();i++) {
f |= f<<nums[i];
}
return f[sum];
}
};
|