相关疑难解决方法(0)

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