子集和
进阶子集和是 0-1 背包的判定版本，只关心"能不能"而非"最大价值"。
// 算法讲解
子集和
输入数组和目标值（最后一个数），判断子集和是否存在。
待机
速度 中
待机 ⌨1bool subsetSum(vector<int>& nums, int target) {
2 vector<bool> dp(target + 1, false);
3 dp[0] = true;
4 for (int x : nums)
5 for (int w = target; w >= x; w--)
6 dp[w] = dp[w] || dp[w - x];
7 return dp[target];
8}
复杂度分析
时间 O(n * target)
空间 O(target)
最优 O(n * target)
最坏 O(n * target)
算法讲解
子集和问题要求判断是否可以从数组中选出若干元素，使它们的和恰好等于目标值 target。
DP 用布尔数组 dp[w] 表示"和为 w 是否可达"，转移方式和 0-1 背包类似。
它是 NP-Complete 问题的伪多项式解法：时间依赖数值大小而非仅输入长度。
在密码学和近似算法中，子集和问题及其变体有重要应用。