Skip to content

Instantly share code, notes, and snippets.

@aashish
Last active August 29, 2015 14:01
Show Gist options
  • Save aashish/c7b75ba28a8f8d0b4b11 to your computer and use it in GitHub Desktop.
Save aashish/c7b75ba28a8f8d0b4b11 to your computer and use it in GitHub Desktop.
Number of possible equations of K numbers whose sum is N
#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}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment