LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i] 表示存在和为 i 的组合

class Solution {
 public:
  bool canPartition(vector<int>& nums) {
    int n = accumulate(begin(nums), end(nums), 0);
    if (n % 2 & 1) {
      return false;
    }
    n /= 2;
    vector<bool> dp(n + 1);
    dp[0] = true;
    for (auto& x : nums) {
      for (int i = n; i - x >= 0; --i) {
        if (dp[i - x]) {
          dp[i] = true;
        }
      }
    }
    return dp[n];
  }
};

• 用 bitset 的每一位 b[i] 表示存在和为 i 的组合

如果 i 满足条件，即 b[i] == 1，要标记 b[i + j] = 1，把 b[i] 左移 j 位即可
b = 0000 0001 表示 0 存在，如果要表示 3 存在，则 b <<= 3 即可，b = 0000 1000
两者进行或运算的结果即表示存在 0 和 3
  0000 0001
| 0000 1000
= 0000 1001

• 题目已说明不超过 200 个元素，每个元素不超过 100，因此总和的一半不超过 10000，最多需要 10001 个标记

class Solution {
 public:
  bool canPartition(vector<int>& nums) {
    if (size(nums) < 2) {
      return false;
    }
    int n = accumulate(begin(nums), end(nums), 0);
    if (n % 2 & 1) {
      return false;
    }
    bitset<10001> b{1};
    for (auto& x : nums) {
      b |= (b << x);
    }
    return b[n / 2];
  }
};