我在解决子集和问题时遇到了困难。
给定一个整数集合(S),需要计算出非空子集,其总和等于给定的目标值(T)。
示例: 给定集合S{4, 8, 10, 16, 20, 22} 目标值T = 52。
限制条件: 集合S的元素数量N限制为8。因此,由于N有一个较小的上限,可以接受NP时间复杂度的解决方案。 时间和空间复杂度并不是真正的问题。
输出:
可能的子集,其总和恰好等于T=52:
{10, 20, 22}
{4, 10, 16, 22}
Wiki和其他一些页面中提供的解决方案尝试检查是否存在这样的子集(YES/NO)。
它并不能真正帮助计算所有可能的子集,如上面的示例所述。
在这个链接中,动态规划方法只给出了一个这样的子集,但我需要所有这样的子集。一个明显的方法是使用暴力计算所有2^N组合,但那将是我的最后手段。
我正在寻找一些编程示例(最好是C ++)或算法,可以计算出这样的子集并带有说明/示例。