题解 | 分割等和子集
题干解析
题设给予我们一个数组，要求我们进行判定所给数组能够拆分为两个总和一致的数组。
算法思路
首先大前提，我们必须知道这个数组所有值的总和，记作sum，当且仅当sum是个偶数时我们才可能将数组拆分为两个等和子集。
同时我们转化问题为，在数组中选择一定数量的元素，使这些元素的总和大小为。于是我们将问题转化为0/1背包问题。设定状态值为dp[i][j]表示使用前i个元素能否填满大小为j的背包。
于是我们有状态转移方程：
设定初始值dp[0][0] = true;开始DP计算即可。
同时由于DP过程状态转移方程只涉及i与i-1，因此可进行滚动优化内存。
实现代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (auto i : nums) sum += i;
if (sum % 2) return false; // 奇数直接返回不行
sum >>= 1; // 在此处总和已减半
vector<bool> dp(sum + 1, false);
dp[0] = true;
int min_ = 0;
// DP，min_是为了防止越界访问，我们不需要考虑大于sum的背包情况
for (auto i : nums) {
min_ = min(min_ + i, sum);
for (int j = min_; j >= i; --j) {
dp[j] = dp[j] || dp[j - i];
}
if (dp[sum]) return true; // 找到立刻返回，其实也可以最后统一返回dp[sum]
}
return false;
}
};
复杂度分析
- 时间复杂度：
- 空间复杂度：
查看18道真题和解析
