忽略相同值元素时，求解子集和问题目标不同子集的时间复杂度

经典单子集查找变体 #

给定集合S与目标值t，仅需找到任意一个和为t的子集时，该问题存在伪多项式时间解法。

输出所有符合条件子集的变体 #

若要求找出S中所有和为t的子集，则不存在伪多项式时间解法。最坏场景下：当集合包含N个0且目标值为0时，需要输出的子集数量为2ⁿ - 1，因此时间复杂度无法低于O(2ⁿ)。

不区分相同值元素的不同子集输出变体 #

当我们将由相同值元素组成的子集视为同一集合（即不区分元素个体，仅关注数值组合）时，输出所有和为t的不同子集的时间复杂度为伪多项式时间O(k*t)，其中：

• k是集合中不同数值的数量
• t是目标和

核心逻辑：通过动态规划，针对每个不同数值，逐步更新可达成的和的集合，并记录对应的组合方式。由于相同数值的元素仅按计数维度处理（选0个、1个…直到该数值的可用次数），而非每个元素单独作为独立选项，因此不会产生指数级的输出量，最终复杂度由不同数值数量和目标和共同决定。

内容的提问来源于stack exchange，提问作者Samuel Bismuth