n_choose_k.rb

#Combinations
# Time complexity: N^K where k = target
# Space complexity: K * N^2
def nchoosek(numbers, target, partial=[])

  if partial.size == target
    puts "#{partial}"
    return
  end
  (0...numbers.length).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    nchoosek(remaining, target, partial + [n]) # partial + [n] creates a new array
  end
end

nchoosek([3,9,8,0,1,2],3)