ruby - Recursive function for combinations -


i'm trying solve following problem :

given 2 integers n , k, return possible combinations of k numbers out of 1 ... n.

i'm doing in ruby , tried implement solution https://gist.github.com/safeng/8156755, result empty.

def combine(n, k)     res = [[]]      return res if k > n || n == 0      sol = []     comb(0, 0, k, n, sol, res)     res end  def comb(start, idx, k, n, sol, res)   if idx == k      res << sol   else     (start..n).to_a.each |i|       sol << (i + 1)       comb(i + 1, idx + 1, k, n, sol, res)       sol.pop     end   end end  print combine(4, 2) #[[], [], [], [], [], [], [], [], [], [], []] 

do have ideas ?

thank you

note (updated):

code works:

def combine(n, k)     res = []      return res if k > n || n == 0      sol = []     comb(0, 0, k, n, sol, res)     res end  def comb(start, idx, k, n, sol, res)   if idx == k      res << sol.dup   else     (start..n - 1).to_a.each |i|       sol << (i + 1)       comb(i + 1, idx + 1, k, n, sol, res)       sol.pop     end   end end 

there's few bugs in code:

you don't need add empty array res when initialize in combine:

res = [] 

when add sol res should duplicate rather pushing reference, otherwise solutions have added res modified when modify sol:

if idx == k     res << sol.dup 

lastly, need loop n-1 (because pushing i + 1 sol):

(start..n-1).to_a.each |i| 

Comments

Popular posts from this blog

wordpress - (T_ENDFOREACH) php error -

Export Excel workseet into txt file using vba - (text and numbers with formulas) -

Using django-mptt to get only the categories that have items -