找到所有从给定集合求和（允许重复）的方法

一尘不染

找到所有从给定集合求和（允许重复）的方法

algorithm

给定一个由n个元素组成的数组（例如[1,2]）和一个数字“ k”（例如6个），找到产生和= k的所有可能方法

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

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)
      } 
   }

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

编辑：如果有人可以给我代码及其soln代码的运行时复杂性，我将不胜感激。:)我认为矿井代码复杂度是Big-O（n ^ w）w = k / avg（arr
[0] .. arr [n-1]）

阅读 249

2020-07-28

共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）

2020-07-28