算法 [Ruby Quiz] 在一组整数中,抽取所有的用加法可算出目标整数的组合

fredwu · 2012年03月01日 · 最后由 bluexuemei 回复于 2014年04月21日 · 3696 次阅读

看到 http://ruby-china.org/topics/1504 这个帖子,那么我也来出一道算法题给大家玩玩吧。

已知两个参数:

一个目标整数,例如 5 一个可用数组,包含一组整数(正负皆可),例如 [-1, 0, 1, 2, 3, 4]

目标:

用数组中的整数(每个整数只能用一次),通过加法,算出目标整数。返回所有满足这个条件的数组组合。

如果目标整数是 5,可用数组是 [-1, 0, 1, 2, 3, 4],那么结果将是:

[1, 4], [2, 3], [-1, 2, 4], [0, 1, 4], [0, 2, 3], [-1, 0, 2, 4], [-1, 1, 2, 3]

做完后可以去看一下我之前写的方案:https://gist.github.com/598577

:)

[Ruby Quiz] 话题挺有意思,建议坛子里可以建个 Ruby Quiz 的节点。:>

难道是太复杂所以没人来尝试么?o_O

@fredwu 我个疑问: 根据题意,[-1,0,1,2,3] 也是正确结果,却在你的输出中没有。

@fredwu 还有就是,0 这个元素可以出现在任意一个正确结果中,那就是说,如果输入的数组有 0 这个元素的话,最后一定是有偶数个正确结果。 你给出的结果是 7 组。漏下上面说的那一组啦 :>

#2 楼 @fredwu 题目看着难懂,我看了一下没明白意思。不如上个简明。

Array.combination 但是 1.8 不支持

@fredwu 在你的基础上修改了一下,你的 combination 这个用法很巧妙~

代码在这里:https://gist.github.com/1948550

class Sumify
  def self.run(num, collection)
    collection.size.times.map { |n| collection.combination(n).to_a }.flatten(1).select { |c| c.inject(:+) == num }
  end
end

这样结果应该就正确了。

似乎 combination(n) 应该改为 combination(n+1)

需要 登录 后方可回复, 如果你还没有账号请 注册新账号