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
Post a Comment