从给定集合中找到所有可以重复使用的数字相加得到给定数字的方法。

Question

给定一个包含n个元素的数组（例如[1,2]）和一个数字k（例如6），找出产生总和等于k的所有可能方法。

对于给定的示例，答案是4，因为：

1. 1 + 1 + 1 + 1 + 1 + 1 = 6 2. 1 + 1 + 1 + 1 + 2 = 6 3. 1 + 1 + 2 + 2 = 6 4. 2 + 2 + 2 = 6

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

我能想到的算法是暴力解法，我们模拟所有可能的情况，并在从给定状态无法达到结果时停止。

 arr[] = [1,2]
    k = 6
   globalCount =0;
   function findSum(arr,k)
   {
      if(k ==0)
         globalCount++
         return
      else if(k<0)
         return

      for each i in arr{
       arr.erase(i)
       tmp = k
       findSum(arr,tmp)
       while(k>=0){
          findSum(arr,tmp -= i)
      } 
   }

我不确定我的解决方案是否是最有效的。请评论/纠正或指出更好的解决方案。

编辑：如果有人能给出我的代码的运行时复杂度和他们的解决方案代码，我将非常感激。:) 我认为我的代码复杂度为Big-O（n ^ w），其中w = k / avg（arr [0]..arr [n-1]）

- Ajeet Ganga

---

分割数理论是研究自然数的分割方式的一个数学分支，即代表正整数n的所有正整数之和。例如，正整数4可以表示为1+1+1+1、1+1+2、1+3、2+2和4等多种方式。一个非负整数的分割数就是它所有不同分割方式的数量。例如，正整数4有5种不同的分割方式，因此其分割数为5。 - Tom Zych

可能是生成一个数字的分区的重复问题。 - templatetypedef

Answer 1

如果你可以不介意复杂的Linq技巧，你可能会发现这个C#的解决方案很有用。幸运的是，Linq的语法读起来有点像英语。这个想法是当k从0开始递增直到达到正确的值时，构建解决方案。每个k的值都建立在前面的解决方案之上。然而，要注意确保找到的新“路径”不是其他路径的重新排序。我通过只计算已排序的路径来解决这个问题（这只需要进行一次比较）。

void Main() {
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) {
        Console.WriteLine (string.Join(" ", way));
    }
}

int[][] GetSumWays(int[] array, int k) {
    int[][][] ways = new int[k + 1][][];
    ways[0] = new[] { new int[0] };

    for (int i = 1; i <= k; i++) {
        ways[i] = (
            from val in array
            where i - val >= 0
            from subway in ways[i - val]
            where subway.Length == 0 || subway[0] >= val
            select Enumerable.Repeat(val, 1)
                .Concat(subway)
                .ToArray()
        ).ToArray();
    }

    return ways[k];
}

输出：

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

它采用动态规划方法，应该比朴素的递归方法更快。我认为。我知道它足够快，可以在几毫秒内计算分解一美元的方式数量。(242)

- recursive

---

如果你没有告诉我，我永远不会知道它是一个编译和执行程序的程序。这太像英语了。 :) - Ajeet Ganga

你能发布一个C或Python版本吗？ - Pankhuri Agarwal

Answer 2

这是分区问题的一个有趣子集。实际上，如果允许所有整数，这个问题有一个封闭形式的解决方案（参见这里和这里）。

对“受限分区函数”进行一些谷歌搜索给了我一些线索。这篇论文提供了一个相当数学严谨的讨论，介绍了几个解决此问题的解决方案，这篇论文也是如此。

不幸的是，我太懒了，没有编写它们。它们的解决方案非常复杂。

- AlexQueue

---

感谢Queequeg找到了问题背后的问题。 :) - Ajeet Ganga

Answer 3

 static void populateSubsetSum(int[]a,int K,int runSum,int idx,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> al){
    if(idx>=a.length || runSum>K)
        return;
    if(runSum==K){
        ans.add(new ArrayList<>(al));
        return;
    }
    ArrayList<Integer> temp=new ArrayList<>(al);
    temp.add(a[idx]);
    populateSubsetSum(a,K,runSum+a[idx],idx,ans,temp);//when repitions of elements are allowed
    populateSubsetSum(a,K,runSum,idx+1,ans,al);
}

调用此函数的方式：

populateSubsetSum(a,K,0,0,ans,new ArrayList<>());//array,sum,initial_sum,global 2d list,temp list

- Sushil Jaiswal