L&#233;o - 2 years ago 65
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
``````

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|
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download