我正在研究这个问题:
该子集和问题需要输入一个组
X = {x1, x2 ,…, xn}的n整数和另一个整数K.问题是,以检查是否存在一个子集X'的X,它的元素之和为K,并发现该子集,如果有任何.例如,如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES,因为该子集X' = {5, 11}具有的总和16.实现Subset Sum的算法,其运行时间至少为O(nK).
注意复杂性O(nK).我认为动态编程可能有所帮助.
我找到了一个指数时间算法,但它没有帮助.
有人可以帮我解决这个问题吗？