比如求 1 到 12 中间 相加之和等于 12 的组合
for a in (1..11) do
for b in (1..11) do
for c in (1..11) do
for d in (1..11) do
for e in (1..11) do
for f in (1..11) do
for i in (1..11) do
for j in (1..11) do
for k in (1..11) do
for l in (1..11) do
for m in (1..11) do
for n in (1..11) do
if a+b+c+d+e+f+i+j+k+l+m+n ==12 then
print 10.chr,a,'+',b,'+',c,'+',d,'+',e,'+',f,'+'i,'+',j,'+',k,'+',l,'+',m,'+',n,'= 12'
end
end
end
end
end
end
end
end
end
end
end
end
end
如果是 24 呢？
(1..12).map{|i| (1..12).to_a.combination(i).select{|a| a.inject(&:+) == 12 } }
=> [[[12]], [[1, 11], [2, 10], [3, 9], [4, 8], [5, 7]], [[1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]], [[1, 2, 3, 6], [1, 2, 4, 5]], [], [], [], [], [], [], [], []]
arr0 =[] arr1=[]
for a in 1..12 b = 12-a arr << a arr << b end
for i in 0.. 11 print "#{arr0[i]},#{arr1[i]}" end
这样子行么？
刚发现，不是两数之和，呆了。。。被你“相加”迷惑了，这是“累加”啊。。。
(1..12).inject([]){|s,i| s + (1..12).to_a.combination(i).select{|a| a.inject(&:+) == 12 }}
=> [[12], [1, 11], [2, 10], [3, 9], [4, 8], [5, 7], [1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5], [1, 2, 3, 6], [1, 2, 4, 5]]
无残留版
数硬币问题 http://rosettacode.org/wiki/Count_the_coins#Ruby
def subset_sum(numbers, target, partial=[])
s = partial.inject 0, :+
# check if the partial sum is equals to target
puts "sum(#{partial})=#{target}" if s == target
return if s >= target # if we reach the number why bother to continue
(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n])
end
end
如果你用 Haskell：
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
好吧我哪有这么牛逼，其实是抄的
est
#7
2015年08月13日
2.1.2 :035 > (1..12).each{|i| (1..12).to_a.combination(i).map{|x| print x if x.inject(&:+)==12 } }
[12][1, 11][2, 10][3, 9][4, 8][5, 7][1, 2, 9][1, 3, 8][1, 4, 7][1, 5, 6][2, 3, 7][2, 4, 6][3, 4, 5][1, 2, 3, 6][1, 2, 4, 5] => 1..12
yakczh
#11
2015年08月13日
可以自动生成上述代码，然后 eval
x=12
s=(1..x).map{|t|"(0..#{x-1}).each{|x#{t}|"}.join
ary=(1..x).map{|i|"x#{i}"}
eval s+"print "+ary.join(",',',")+',"\n" if '+ary.join("+")+"==#{x}"+"}"*x
yakczh
#15
2015年08月13日
(12) (1,11) (11,1) (2, 10) (10,2) (3, 9) (9, 3) (4, 8) (8,4) (5, 7) (7,5) (6, 6) (1, 1, 10) (1,10,1) (10,1,1) ...
这种的
est
#17
2015年08月14日
arth
#18
2015年08月14日
使用回溯法。dfs 即可。很简单，帮楼主写了一个。试试看。
def sum_array_equals_to(target)
elements=[]
target.times{|i| elements<<i+1}
result=[]
dfs(target,0,[],elements,result)
result.uniq
end
def dfs(target,curSum,curArray,elements,result)
result<<curArray.sort if target==curSum
elements.each do |e|
if curSum+e<=target
elements-=[e]
dfs(target,curSum+e,curArray+[e],elements,result)
elements+=[e]
end
end
end
p sum_array_equals_to(6)
