def gen_comb(list,n)
  if n==0
    yield([])
  else
    (list.size-n+1).times do |i|
      gen_comb(list[i+1..-1],n-1) do|ls|
        yield([list[i]]+ls)
      end
    end
  end
end

def comb_num(list,n,sum)
  ret=[]
  gen_comb(list,n) do |a|
    ret<<=a if (a.inject(0){|r,e| r+=e})==sum
  end
  ret
end

def comb_array(list,n)
  ret=[]
  gen_comb(list,n) do |a|
    ret<<=a if a.inject{|r,e| break unless (r&e).empty?;r+=e}
  end
  ret
end

def maho(n)
  m=n**2
  sum=m*(m+1)/2/n
  comb_array(comb_num((1..m).to_a,n,sum),n)
end

start_time = Time.now
puts maho(4).size
puts Time.now-start_time