子集和与划分
使用选定子集达到目标值
子集和与划分 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
子集和问题
给定一些数字和一个目标值，是否存在某个子集，其元素之和恰好等于该目标值？这就是价值等于重量的背包问题。
布尔 DP，而不是价值
这里跟踪的是可达性，而不是最大值。令 dp[s] 在存在某个子集的和恰好为 s 时取 True。
dp = [False] * (target + 1)
dp[0] = True零总是可达的
空子集的和为零，因此 dp[0] 初始为 True。其他所有和初始为 False，直到某个数字证明它们可达。
状态转移
对于每个数字，如果 s - num 之前可达，就将 s 标记为可达。一个数字可以让许多和变为 True。
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]再次反向遍历
每个数字最多使用一次，因此内层循环要反向运行，就像 0/1 背包一样。正向遍历会重复使用同一个数字。
读取判定结果
处理完所有数字后，dp[target] 就能回答问题。True 表示存在有效子集，False 表示无法实现。
进入等和划分
划分问题要解决的是：能否将数组分成两个元素和相等的部分？它可以直接转化为子集和问题。
将总和除以二
如果总和为奇数，就不可能分成两个相等的部分，因此可以立即回答否。否则，目标值就是 total // 2。
total = sum(nums)
if total % 2:
return False
target = total // 2复用子集和
现在只需判断是否存在一个子集，其和达到 total // 2。如果其中一半达到目标值，剩余元素就会自动组成匹配的另一半。
复杂度
开销为 n 乘 target 级别，属于伪多项式复杂度。当目标值较小时速度较快，而总和很大时则会变慢。
一类问题的通用解法
子集和、划分问题和 0/1 背包共享同一个核心。识别出选或不选的结构后，您就能复用同一个循环。
快速检查
请测试划分问题的归约。
回顾
您使用布尔 DP 和反向循环解决了子集和问题，然后将划分归约为达到总和 // 2。同一个核心，又解决了新的问题。✅
常见问题解答
「子集和与划分」课时是免费的吗？
是的 — 「子集和与划分」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「子集和与划分」这节课中我会学到什么？
使用选定子集达到目标值 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「子集和与划分」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。