在经典的子集和问题中，存在一个集合 S 和一个目标 t，目标是找到 S 的一个子集，其和为 t。该变体具有伪多项式时间解。
在子集和问题的一个变体中，目标是找到 S 中所有和为 t 的子集。此变体没有伪多项式时间解；请参阅此处的答案：使用动态规划在 Python 上从子集和问题中获取所有子集。其中一条评论解释说，在最坏的情况下，当你有 N 个零，并且所需的和也为零时，你将需要输出所有 2^n - 1 个子集——因此不可能比 O(2^n) 更优。
如果我们不区分两个具有相同值的项目（例如，如果两个集合由一些具有相同值的项目组成，则它们被视为同一集合）——输出总和为 t 的所有不同子集的运行时复杂度是多少？
我认为修改后的问题的最坏情况是集合 包含从
-m到 的所有整数m，求 的和0。这个集合完全没有重复项。在这种情况下
n = 2m+1。由于n和m以常数因子变化，因此就大O而言，它们是相同的。最大可能的和为 ，
m*(m+1)/2最小可能的和为-m*(m+1)/2。这意味着2^n可能的子集被划分到O(n^2)可能的和之间。这会产生 的直接下限O(2^n / n^2)，它是指数级的。使用中心极限定理可以稍微改进该下限。考虑一个随机集的情况。它是
n随机变量的和。每个随机变量都有各自的均值i和方差(i/2)^2。随机变量之和的均值为0，方差为。因此，它近似于一个均值为、标准差为O(n^3)的正态分布。这意味着求和的方法数量应该是。0O(n^(3/2))0O(2^n / n^(3/2))在最坏的情况下，当你有 N 个零，且所需的和也为零时，你必须输出 N 个不同的集合，每个集合包含 1、2、3……N 个零。因此，复杂度为 O(n)。