Léo Léo - 6 months ago 15
Ruby Question

Recursive function for combinations

I'm trying to solve the following problem :


Given two integers n and k, return all possible combinations of k
numbers out of 1 ... n.


I'm doing it in ruby and tried to implement this solution https://gist.github.com/safeng/8156755, but my result is always 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 do |i|
sol << (i + 1)
comb(i + 1, idx + 1, k, n, sol, res)
sol.pop
end
end
end

print combine(4, 2) #[[], [], [], [], [], [], [], [], [], [], []]


Do you have any ideas ?

Thank you

NOTE (UPDATED):

Code that 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 do |i|
sol << (i + 1)
comb(i + 1, idx + 1, k, n, sol, res)
sol.pop
end
end
end

Answer

There's a few bugs in your code:

You don't need to add an empty array to res when you initialize it in combine:

res = []

When you add the sol to res you should duplicate it rather than pushing a reference, otherwise the solutions that you have already added to res will get modified when you modify sol:

if idx == k
    res << sol.dup

Lastly, you only need to loop to n-1 (because you are pushing i + 1 to sol):

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