的組合

Question

我試圖解決以下問題遞歸函數：

給定兩個整數n和k，返回k的所有可能的組合 號碼的開出的1 ... N。

我做它的紅寶石，並試圖實施該解決方案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) #[[], [], [], [], [], [], [], [], [], [], []] 

你有什麼想法嗎？

謝謝

NOTE（修訂版）：

代碼工作：

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 = [] 

當您添加，當你修改sol的sol到res你應該重複它，而不是推的引用，否則您已經添加到res的解決方案將得到修正：

if idx == k 
    res << sol.dup 

最後，您只需循環到n-1（因爲您推i + 1至sol）：

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