初学者，请大神指教

n, m = gets.split.map! { |e| e.to_i }
(1..n).each { |i| (1..n).to_a.combination(i) { |arr| print arr.join("+"), "\n" if arr.inject { |sum, x| sum + x } == m } }

这次我也一行党...

def coushu(n, m)
  (1..n).each { |i| (1..n).to_a.combination(i).each { |j| p j if j.inject(:+) == m } }
end

#2 楼 @blacktulip

def coushu(n, m)
  (1..n).each{|i| [*1..n].combination(i).each { |j| p j if j.inject(:+) == m }}
end

小改一下作业。这个在算法上叫枚举法吧。

#2 楼 @blacktulip 这种算法是穷举法，效率非常低，求高效算法

状态转移大发 d[n][m] = d[n-1][m-n] + d[n-1][m]

用递归做，比较好一些吧？

#6 楼 @yfractal 就是 01 背包，动态规划破之

如楼上所说：

def coushu(n, m, confirmed=[], &b)
    if n == 0
        if m == 0
            yield confirmed
        end
    else
        coushu(n-1, m-n, confirmed + [n], &b)
        coushu(n-1, m, confirmed, &b)
    end
end

coushu(10, 15) {|x| p x }

#8 楼 @Alexander &b 在这里起什么作用？

#8 楼 @Alexander 如果给定任意一个数组 arr，随意取几个数 , 使其和等于 m , 要求将其中所有的可能组合列出来，程序又该如何写？

availables = [1,3,..10....]

想要凑起来得 m 有两种情况，1，用 availables 的第一个数，2，不用 availables 的第一个数。然后递归。

对于第一种情况，m = m- availablse[0]，下一次的 availables 刨除第一个数。 对于第二种情况，m = m，下一次的 availables 刨除第一个数。

大体思路就是分两种情况，然后做递归。 #7 楼 @saiga 突然发现，我不知道 01 和动态规划。。。掩面 。。。

#11 楼 @yfractal 背包问题理解起来很费力，哪里有通俗易懂的资料？

#11 楼 @yfractal 我就知道个名字，真让我写也写不出... _ (:з」∠)_

#12 楼 @bluexuemei MIT 有一个系列课程《计算机科学及编程导论》，里面有讲到背包问题，动态规划和贪心算法，for python

#12 楼 @bluexuemei 程序的构造与解析 应该有这道题。。。你可以问问别人。 或者 http://www-inst.eecs.berkeley.edu/~cs61a/sp14/ ，也应该有类似的题，我忘了在哪了。。。都是关于找钱的，就是有几种硬币，然后一凑个整数。

觉得递归都不容易懂，反正我学递归学了好久。。。

#15 楼 @yfractal 中兴 10 年面试题 http://blog.csdn.net/v_july_v/article/details/6419466

#13 楼 @saiga :) 觉得能写出代码的人都很牛！比如 8 楼

#16 楼 @saiga :plus1:

#15 楼 @yfractal 同感，递归也是个难啃的骨头。真佩服那些算法高手、递归神人！

#14 楼 @saiga 英文的，有没有中文的视频？

#20 楼 @bluexuemei http://v.163.com/special/opencourse/bianchengdaolun.html

#21 楼 @saiga 太感谢你了

#8 楼 @Alexander #11 楼 @yfractal 递归很精彩，学习了

再请问给 4 个数的数组，算 24 点做递归，有优先级的计算和表示问题。

这次我想到的方法跟@blacktulip是一样的 def coushu(n,m) result =.each {|i| [*1..n].combination(i).each {|j| result << j if(j.inject(:+)==m) }} return result end

p coushu(2,2) p coushu(5,7)

[[2]] [[2, 5], [3, 4], [1, 2, 4]]

#24 楼 @ucooling 这样的思路很简单，但是效率低，不可取

之前写过凑 24 点的，可以借鉴一下 https://gist.github.com/piecehealth/9342052

#25 楼 @bluexuemei 学习 Ruby 时间不长，还需要学习，觉的 8 楼的方法比较牛逼，之前学过递归，但是一直没有用的意识