Léo - 4 months ago 5

Ruby Question

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

`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

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|
```

Source (Stackoverflow)

Comments