找到所有的方法，总结给定的数字（以允许重复）从给定 [英] Find all ways to sum given number (with repetitions allowed) from given set

问题描述

给定的阵列（例如，[1,2]）的n个元素和多个数k的（例如6），发现所有可能产生的总和= K方法

Given an array (e.g. [1,2]) of n elements and a number 'k' (e.g. 6), find all possible ways to produce the sum = k

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

For given example answer would be 4 because

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

这个算法我能想到的是蛮力，我们模拟所有可能的方案，并停止从给定的状态，当我们无法达到的结果。

The algorithm I could think of is by brute force, we simulate all possible scenarios, and stop when from given state we can not reach result.

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

我不知道如果我的解决方案是最有效的一出在那里。请评论/更正或显示指针，以更好的解决方案。

I am not sure if my solution is most efficient one out there. Please comment /correct or show pointers to better solutions.

编辑：难道真的AP preciate，如果有人可以给我运行时我的code和他们的SOLN code的复杂性。 :) 矿山code的复杂性，我认为是大O（N ^ w）的W = K / AVG（ARR [0] ...改编[N-1]）

EDIT : Would really appreciate if someone can give me runtime complexity of my code and their soln code. :) Mine code complexity I think is Big-O( n^w ) w = k/avg(arr[0]..arr[n-1])

推荐答案

如果你愿意原谅看中LINQ的技巧，你可能会发现这个C＃的解决方案非常有用。幸运的是LINQ读取有点像英语。我们的想法是，直到达到其正确的价值建立起来的解决方案， K 从0开始递增。对每个值k 建立在previous解决方案。有一件事你必须留意，虽然是为了确保新的办法你发现没有被重新排序他人。我解决了这个只计算其作为有效的，如果他们来分类的。 （这是只有一个单一的比较）

If you're willing to excuse the fancy linq tricks, you might find this C# solution useful. Fortunately linq reads kind of like english. The idea is to build up the solutions as k starts from 0 and increments until it reaches its correct value. Each value of k builds on the previous solutions. One thing you have to watch for though is to ensure that the new "ways" you're finding are not re-orderings of others. I solved that by only counting them as valid if they're sorted. (which was only a single comparison)

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）

It uses a dynamic programming approach and should be faster than a naive recursive approach. I think. I know it's fast enough to count the number of ways to break a dollar in a few milliseconds. (242)

这篇关于找到所有的方法，总结给定的数字（以允许重复）从给定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！