c# - 指定数量集的任意加法组合，达到特定目标值

Question

我正在寻找一种方法来获得所有可能的数字组合以达到指定的目标值。 数字集的值可以重复。

例如:
号码组为4、5、6、7、8
我想要达到的值是 16。

因此，我想要这样的东西:

4+4+4+4  
4+4+8  
5+5+6  
...  

我找到的任何解决方案都没有重复，如下所示:
Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number

提前致谢!

Answer 1

您也可以使用相同的递归方法。但是不要从可能的项目集中删除用过的项目。如果你想区分 a+b+a 和 a+a+b 变体 - 遍历所有集合，如果不是 - 只遍历当前位置的项目。

function Partitions(Sum, A[], CurIdx, Result)
  if Sum = 0
     output Result
  //all variants with permutations
  for i = 0 to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i, Result + A[i])

  //variants without permutations
  for i = CurIdx to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i, Result + A[i])

  // you don't need this, just for record:  
  //variant without repeats essentially does the next:
        Partitions(Sum - A[i], A[].Remove i-th item, i, Result + A[i])

   or (note  i+1 start point for the next recursion level)

  for i = CurIdx to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i + 1, Result + A[i])