子集和求和[动态规划]

文章目录

1. 子集和求和[动态规划]

Subset Sum问题算是一个著名的npc问题。给定一个整数数列和一个整数，求出在原数列中是否存在子集的和为这个整数。这里我们加个限制就是这些整数都为正整数。那么问题可以用动态规划来求解，它和01背包问题很像。

我们设isSubsetSum[i][j]表示数列a[0]到a[i-1]是否存在子集的和为j，如果存在设为true；不在设为false。

那么这个问题的子问题就可以这样写isSubsetSum[i][j] = isSubsetSum[i-1][j] || isSubsetSum[i-1][j-a[i]]。前者表示在少一个元素的情况下，和是否还为j；后者表示去掉a[i]这个元素，和是否为j-a[i]。那么isSubsetSum[i][j]的值实际上就是看这两个情况是否至少存在一个，只要存在一个，那么就存在子集的和符合条件的情形。

这样的话填完这个表需要O(n*m)，n表示元素的大小，m表示和。填写一个元素需要O(1)的时间。所以这个问题的复杂度是O(n\*m)。