Subset Sum Problem
nums 中存放着正整数，target 是一个正整数。你能从中选出一些值，每个位置最多选一次，使它们的和恰好等于 target 吗？如果可以，返回 true；如果没有可行的选法，返回 false。
函数
- numsinteger-array
- 你可以选择的正数
- targetinteger
- 选中的值必须达到的准确总和
- 返回值boolean
- 当部分值相加后恰好等于 target 时为 true，否则为 false
约束条件
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
示例
- 输入
- nums = [8, 3, 11, 5, 7]target = 15
- 输出
- true
- 解释
- 8 + 7 = 15，所以答案是
true。选择 3 + 5 + 7 也可以，选一组就够了。
- 输入
- nums = [6, 9, 12, 15]target = 20
- 输出
- false
- 解释
- 每个值都是 3 的倍数，所以它们的和也都是 3 的倍数。20 不是，所以答案是
false。
- 输入
- nums = [4, 1, 2]target = 8
- 输出
- false
- 解释
- 这三个值加起来是 4 + 1 + 2 = 7，小于 8，所以没有任何选择能达到这个值，答案是
false。
进阶
两个相等的值在不同位置时算作不同的选取。有多少种选取能得到 target？
提示
逐个打开提示，每个都会多透露一点。
从
nums[0]开始。如果你选了它，其他值之和必须是target-nums[0]。如果没有选它，其他值之和必须是target。这两个问题本质相同，只是数组更短。位置
i及其后面的值能否组成和为r的结果，只取决于i和r，而且r不会超过target。因此，最多大约有 200 × 10^4 个不同的问题，每个问题只需要回答一次。为从 0 到
target的每个和设置一个布尔值，初始时只有和 0 可达。逐个添加数值：如果和s-num已经可达，那么和s就变为可达。从大到小更新各个和，这样同一个值就不会被使用两次，然后读取target处的答案。
题解
每个值都对应一次是或否的选择，因此 200 个值会产生 2^200 种选择。不过，只需考虑不超过 target ≤ 10^4 的和。记录目前这些值能够组成哪些和：每个新值都会按其大小移动这份记录，搜索就变成一个由 n × target 个布尔值组成的表。
选择或跳过每个值
结果正确，但无法在最大的测试中运行完毕
思路
canMake(i, remaining) 会判断从位置 i 开始的值能否恰好组成 remaining。如果 nums[i] 不超过剩余值，就选它，这样其余值还需要组成 remaining-nums[i]；如果这样行不通，就跳过它。每次选择都代表一条路径，因此只要存在可行的选择，搜索就能找到。
如果不存在可行的选择，它就会遍历所有路径。有 200 个 3 的倍数，每个数都不超过 300，目标值为 9998。没有任何选择可行，但任取 33 个值的总和都小于目标值：路径超过 10^37 条。
算法
- 编写
canMake(i, remaining)。 remaining为 0 表示选择已完成：返回 true。如果没有剩余数值，但仍有目标需要凑出，则返回 false。- 如果
nums[i] ≤ remaining且canMake(i+1, remaining-nums[i])为 true，则返回 true。 - 否则返回
canMake(i+1, remaining)。 - 返回
canMake(0, target)。
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)填写可达总和表
思路
递归只依赖一个位置和一个介于 0 与 target 之间的剩余和，而且许多路径会到达相同的位置和剩余和。因此，改用填表法。made[i][s] 表示从前 i 个值中选取一些数，恰好得到和 s 时为真；不选任何数时，和为 0。设 num = nums[i-1]，如果不选 num 时已经得到和 s，即 made[i-1][s] 为真；或者在 s ≥ num 时，选 num 能补足 s-num，即 made[i-1][s-num] 为真，那么和 s 就可以得到。
在第一个示例中，处理完 8 后，可得到的和是 0 和 8。3 可以得到 3 和 11，11 只能得到 14，5 可以得到 5 和 13，而 8 + 7 可以得到 15。在数据范围的上限，表有 201 × 10001 个单元格，大约需要 2 × 10^6 步。
算法
- 将
made初始化为 n+1 行、target+1 列的布尔值表，所有值都设为 false。将made[0][0]标记为 true，表示不选任何数。 - 第
i行处理值num = nums[i-1]，其中i从 1 到 n。 - 对于从 0 到
target的每个和s，将made[i][s]设为made[i-1][s]。 - 如果
s ≥ num且made[i-1][s-num]为 true，则将made[i][s]设为 true。 - 返回
made[n][target]。
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]一行求和结果，从顶部更新
思路
每一行只读取它前一行的内容，因此可以用一个数组 made[s] 来保存结果。向上覆盖它时，某个值就会被重复使用：对于 nums = [5] 和目标值 10，s = 5 会变为 true，然后 s = 10 会读取刚写入的条目，于是 5 被用了两次。
改为从 target 向下遍历到 num。读取 s-num 时会访问一个尚未被遍历过程改写的较小位置，因此读到的是处理 num 之前那一行的内容。一个和一旦能组成，就会一直能组成，因此只要 made[target] 为 true，就可以立即停止。内存占用降到 target + 1 个布尔值。
算法
- 先创建一个长度为
target + 1的布尔数组，其中只有made[0]为 true。 - 按顺序取值。对于每个
num，让s从target递减到num。 - 只要
made[s-num]为 true，就将made[s]标记为 true。 - 一旦
made[target]被标记，就立即返回true。 - 如果先用完所有值，答案就是
false。
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
易错点和边界情况
- 向上遍历和时，会重复使用同一个值：对于
[3]，目标值为 9 时会得到 true。 - 忘记设置
made[0] = true。每个和都基于空选择构建，因此所有答案都会是 false。 - 先选最大的值。对于
[6, 5, 5]，目标值为 10 时，取 6 后还剩 4，无法凑出这个值，而 5 + 5 = 10。 - 大于
target的值（例如[10000]，目标值为 1）必须不产生任何影响。Swift 的num...target会停止程序，而 R 的(num+1):(target+1)会倒序计数，因此要先检查num ≤ target。 - 在 Lua 和 R 中，和
s对应的条目位于索引s + 1处。
常见问题4
子集和问题的时间复杂度是多少？
这个表格的时间复杂度为 O(n × target)，对于 200 个值和目标值 10^4，约需 2 × 10^6 步；只保留一行可将空间复杂度降到 O(target)。计算量取决于目标值的数值大小，因此这种方法是伪多项式的，对于 10^18 这样的目标值毫无用处。一般来说，子集和问题是 NP 完全问题。
子集和问题与等和分割问题和 0/1 背包问题有什么关系？
等和子集划分问题就是目标为 target = total / 2 的子集和问题，但要先检查总和是否为偶数。子集和问题是一种 0/1 背包问题，其中每个值的重量就是它自身，而且背包必须恰好装满，因此表中存储的是布尔值，而不是最优值。
子集和问题也适用于负数吗？
这个思路可行，但上面的代码不行。存在负数时，可达的和从负数总和到正数总和，因此要将每个索引都偏移最低和，再用同样的方法填充这一行。大于剩余和的值不能再跳过。
怎样找出哪些值能得到目标值？
保留完整的表格，并从 made[n][target] 开始。每次向上移动一行：如果 made[i-1][s] 为 true，则不需要 nums[i-1]；否则记录它，并从 s 中减去它。当总和为 0 时停止，此时得到一种有效的选取方式。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isSubsetSum(nums, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [8, 3, 11, 5, 7] target = 15
预期输出
true