01.Introduction.pdf P34
问题可以描述为：给一个整数集合，问是否存在某个非空子集，使得子集内中的数字和为某个特定数值。例：给定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因为子集{−3, −2, 5}的数字和是0。这个问题是NP完全问题。
这个问题不是背包问题吗，为什么说没有多项式时间的解法？
wiki上称背包的dp解法为伪多项式时间。
大概意思应该是这样：
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。
也就是说，背包dp的解法是 O(nU) ，U 为数据范围。但是严格的理论指的多项式时间复杂度是输入的总二进制位数的多项式。
例如，对于输入nums = [3, 7, 14]，要算上这几个数的总二进制位数（9位）。这个输入的位数才是输入规模，而不是 nums.size() == 3 。
为什么用输入的位数来衡量输入？
图灵机模型的计算就是要考虑位数。上面的 O(nU) 虽然是多项式，但不是输入位数的多项式。
wiki的例子，按位数来算会变成指数级别的算法：
在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的素数2开始，到 $\sqrt {N}$ 为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约$\sqrt {N}$次整数除法，即其时间复杂度为 $O(\sqrt {N})$，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的幂，因此素性测试问题的时间复杂度用D表示应为$O(2^{D/2})$ （这里把单次运算视作了O(1)应该）。因此，上述算法是一个伪多项式时间算法。
其它被证明只具有伪多项式时间算法解的问题有背包问题，子集合加总问题。