找到给定集合中给定数量(允许重复)的所有方法

Question

给定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])

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)