排列数组中的数字以总计一个数

Question

我已经给出了一个数组。我想查找数组的所有排列，因此它总和为特定的数字。
示例
Array a =[2,3,5 ,1]
目标= 8
解决方案：[2,2,2,2]，[5,3]，[3,3,2]，[5,2,1]以及所有可能的组合
请提供我是一种解决这个问题的方法，我面临的问题是如何处理重复的元素。目标是10^6的大量。 我认为它是一样的This theory

Answer 1

您正面临典型的Subset Problem。无论你如何表达，这个问题的最坏情况下的复杂性都是指数级的。你可能会发现很好的多项式时间近似值，但对于一般情况来说奇迹仍然有效。