Number of possible equations of K numbers whose sum is N

combination.rb

#Input: K, N (where 0 < N < ∞, 0 < K < ∞, and K <= N)
#       Number of possible equations of K numbers whose sum is N
#
#Example Input: N=10 K=3
#
#Example Output:
#Total unique equations = 8
#1 + 1 + 8 = 10
#1 + 2 + 7 = 10
#1 + 3 + 6 = 10
#1 + 4 + 5 = 10
#2 + 2 + 6 = 10
#2 + 3 + 5 = 10
#2 + 4 + 4 = 10
#3 + 3 + 4 = 10
#
#For reference, N=100, K=3 should have a result of 833 unique sets.


print "Number of possible equations of  "
$k = gets.chomp.to_i
print "whose sum is "

$n = gets.chomp.to_i
$t = 0

def combination(k,x=[])
  return if (k.zero? || k > $n)
  1.upto($n) do |x1|
    unless x.empty?
       next if x.last > x1
    end
    y = [x1]
    z = x + y
    combination(k-1, z)
    if k == 1
      if (z.inject{|sum,x| sum + x } == $n)
        $t = $t + 1
        puts z.join(',')
      elsif (z.inject{|sum,x| sum + x } > $n)
        next
      end
    end
  end
end

puts "Possible equations without duplicates are : "
combination($k)

puts "Total possible equations are : #{$t}"