416. 分割等和子集

发表于 分类于 阅读次数： Waline： 本文字数： 202 阅读时长 ≈ 1 分钟

考点

  • 01背包

思路

01背包的模板题，看题解区复习即可

核心思路就是，每个元素有选和不选两种状态，已经默认分成两类集合了

可以得到下面代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  static const int maxn = 2e2 + 50, maxm = 1e4 + 50;
  bool canPartition(vector<int>& nums) {
    int m = 0, n = nums.size();
    bool f[maxm];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) m += nums[i];
    if(m&1) return 0;
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = m / 2- nums[i]; j >= 0; --j) {
        if (f[j]) f[j +nums[i]] = 1;
      }
    }
    return f[m / 2];
  }
};

加上位运算优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
 public:
  static const int maxn = 1e4 + 50;
  bool canPartition(vector<int>& nums) {
    int m = 0, n = nums.size();
    for (int i = 0; i < n; ++i) m += nums[i];
    if (m & 1) return 0;
    bitset<maxn> f;
    f[0] = 1;
    for (int i = 0; i < n; ++i) f |= f << nums[i];
    return f[m / 2];
  }
};