ruby - 组合的递归函数

Question

我正在尝试解决以下问题:

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

我在 ruby​​ 中做这件事并试图实现这个解决方案 https://gist.github.com/safeng/8156755 ，但我的结果总是空。

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) #[[], [], [], [], [], [], [], [], [], [], []]

你有什么想法吗？

谢谢

注意(更新):

有效的代码:

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 1

您的代码中存在一些错误:

在 combine 中初始化 res 时不需要向 res 添加空数组:

res = []

当您将 sol 添加到 res 时，您应该复制它而不是推送引用，否则您已经添加到 res 的解决方案> 将在您修改 sol 时修改:

if idx == k
    res << sol.dup

最后，你只需要循环到n-1(因为你将i + 1推到sol):

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