ruby - 从数组中生成组合，其中==指定数量？

我需要从denom_arr中得到所有可能的数字组合，它们等于amt。

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

本案将产生：
[4, 4, 1, 1]
[3, 3, 3, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[4, 3, 1, 1, 1]
[4, 3, 3]
. ……（其他情况…）
问题是我写的代码在1-3之后被破坏了，我不确定如何使它在同一个索引上循环以获得case4-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

更新
我知道这可以通过递归和记忆/动态编程技术来实现，但是为了测试一个理论，我试图严格地在循环中实现这一点。

最佳答案

我会递归地这样做

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]
  #    ]

虽然这可能是低效的，因为它重复工作，这可以通过使用动态编程（本质上，记住递归函数的结果）来缓解。
更新这里是一个迭代的解决方案：

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

这实际上是针对问题的动态规划算法。
所以，如果你斜视它，你会发现它实际上在做什么，就是用递归算法计算0到amt数组中所有可能的和，但不是递归调用，而是在sums中查找一个我们事先计算过的值。
这是因为我们知道在sums之前不需要sums[i]。

关于ruby - 从数组中生成组合，其中==指定数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24066192/