1

I need to get all the possible number combinations from denom_arr which equal the amt.

denom_arr = [4,3,1]
amt = 10

This case would produce:

  1. [4, 4, 1, 1]
  2. [3, 3, 3, 1]
  3. [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  4. [4, 3, 1, 1, 1]
  5. [4, 3, 3]
  6. . . . (other cases...)

Problem is the code I wrote is breaking after 1-3 and I'm not sure how to make it loop over the same index to get case 4-6+

set, sets = [], []
i = 0
loop do
i = 0 if denom_arr[i].nil? 

  loop do
    set << denom_arr[i]
    break if set.inject(:+) > amt
  end

  set.pop if set.inject(:+) > amt

  if set.inject(:+) == amt
    sets << set
    set = []
    denom_arr.shift
  end

i += 1
sets
break if denom_arr.empty?
end

UPDATE

I know this can be done with recursion with memoization/dynamic programming techniques, but I am trying to do this strictly in a loop for the sake of testing a theory.

MrPizzaFace
  • 7,807
  • 15
  • 79
  • 123
  • What about [4,3,1,1,1]? – BroiSatse Jun 05 '14 at 17:17
  • @BroiSatse yep good catch.. I felt like I was missing something.. Question updated. – MrPizzaFace Jun 05 '14 at 17:19
  • There's a lot of other cases: 4 and 1's, two 3's and 1's, one three and 1's, ... – MxLDevs Jun 05 '14 at 17:22
  • @MxyL yes correct... I'm just really concerned with the shortest case.. – MrPizzaFace Jun 05 '14 at 17:27
  • What theory would that be? – MxLDevs Jun 05 '14 at 17:42
  • That recursion is not the best practice. – MrPizzaFace Jun 05 '14 at 17:44
  • @go____yourself: That would be generally correct, recursion tends to have extra overhead, but tends to be easier to implement in a number of cases. You could have simply searched SO for "recursion verse iteration", and found something like this: [recursion verse iteration](http://stackoverflow.com/questions/15688019/recursion-versus-iteration). So it depends on if the programmer's time is more or less important than the runtime and by how much. – Nuclearman Jun 05 '14 at 17:48
  • @Nuclearman that's completely understandable but I like to learn by taking a hands on approach .. My time is only worth as much as my ability. StackOverflow is place I come to for technical questions if I get stuck in the process. Point being.. I want to see it for myself and I want to learn from implementing it myself. And if I can't figure out how to implement it myself, ask SO community for help. :) – MrPizzaFace Jun 05 '14 at 18:01
  • @go____yourself: Fair enough, in that case asQuirreL seems to have what you are looking for. – Nuclearman Jun 05 '14 at 18:06
  • @Nuclearman yes sort-of I gave him the tick for showing a working iterative solution but I would like to see it explained. – MrPizzaFace Jun 05 '14 at 18:09

1 Answers1

5

I would do this recursively

def possible_sums(arr, amt)
  return [[]] if amt == 0
  return []   if amt < 0

  arr.reduce([]) do |sums, e|
    sums.concat(
      possible_sums(arr, amt-e)
        .map { |sum| sum.unshift(e).sort }
    )
  end.uniq
end

p possible_sums([4,3,1], 10)
  # => [
  #      [1, 1, 4, 4], [3, 3, 4], [1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 4], 
  #      [1, 3, 3, 3], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 3], 
  #      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  #    ]

Although this is potentially inefficient in that it repeats work, this can be alleviated by using dynamic programming (essentially, memoizing the results of the recursive function).

UPDATE Here is an iterative solution:

def possible_sums_it(arr, amt)
  sums = Array.new(amt+1) { [] }
  sums[0] << []

  (1..amt).each do |i|
    arr.each do |e|
      if i-e >= 0
        sums[i].concat(
          sums[i-e].map { |s| [e, *s].sort }
        )
      end
    end

    sums[i].uniq!
  end

  sums[amt]
end

This is in fact the dynamic programming algorithm for the problem.

So if you squint at it just right, you'll see that essentially what it is doing, is calculating all the possible sums for 0 up to amt into the sums array, using what is basically the recursive algorithm, but instead of the recursive call, we lookup a value in sums that we have calculated beforehand.

This works because we know that we won't need sums[i] before sums[j] for j < i.

amnn
  • 3,657
  • 17
  • 23