關於遞歸DFS的2個問題

/* 
Problem 22 Generate Parentheses: 
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" 
*/ 

public List<String> generateParenthesis(int n) { 
    List<String> list = new ArrayList<String>(); 
    backtrack(list, "", 0, 0, n); 
    return list; 
} 

private void backtrack(List<String> list, String str, int open, int close, int max){ 

    if(str.length() == max*2){ 
     list.add(str); 
     return; 
    } 
    if(open < max) 
     backtrack(list, str + "(", open + 1, close, max); 
    if(close < open) 
     backtrack(list, str+")", open, close+1, max); 
}

這是LeetCode上的一個流行解決方案，我知道DFS理論，我只是無法得到兩點。關於遞歸DFS的2個問題

在遞歸函數，有兩個選項添加後「（」，要麼添加一個「（」或添加一些「）」，但代碼是由升轉跌，怎麼可以把這些代碼過程中的其他解決方案執行除了（（（）））。 Like（（）（）），它是如何在兩個後面添加'）'的（'
完成一個解決方案後，將它添加到列表並返回，它是如何在返回後獲取其他解決方案嗎？是不是說這個方法會在返回後結束？關於Java的新學習器，感謝您的詳細解答

來源

2016-02-12 StevenUpForever

我插入這條線在你backtrack()方法的頂部：

System.out.println("backtrack(" + list + ", \"" + str + "\", " + 
        open + ", " + close + ", " + max + ")");

下面是它生成N = 3，我認爲這將有助於您瞭解遞歸在這裏工作。

backtrack([], "", 0, 0, 3) 
-backtrack([], "(", 1, 0, 3) 
--backtrack([], "((", 2, 0, 3) 
---backtrack([], "(((", 3, 0, 3) 
----backtrack([], "((()", 3, 1, 3) 
-----backtrack([], "((())", 3, 2, 3) 
------backtrack([], "((()))", 3, 3, 3) 
---backtrack([((()))], "(()", 2, 1, 3) 
----backtrack([((()))], "(()(", 3, 1, 3) 
-----backtrack([((()))], "(()()", 3, 2, 3) 
------backtrack([((()))], "(()())", 3, 3, 3) 
----backtrack([((())), (()())], "(())", 2, 2, 3) 
-----backtrack([((())), (()())], "(())(", 3, 2, 3) 
------backtrack([((())), (()())], "(())()", 3, 3, 3) 
--backtrack([((())), (()()), (())()], "()", 1, 1, 3) 
---backtrack([((())), (()()), (())()], "()(", 2, 1, 3) 
----backtrack([((())), (()()), (())()], "()((", 3, 1, 3) 
-----backtrack([((())), (()()), (())()], "()(()", 3, 2, 3) 
------backtrack([((())), (()()), (())()], "()(())", 3, 3, 3) 
----backtrack([((())), (()()), (())(),()(())], "()()", 2, 2, 3) 
-----backtrack([((())), (()()), (())(),()(())], "()()(", 3, 2, 3) 
------backtrack([((())), (()()), (())(),()(())], "()()()", 3, 3, 3)

破折號表示堆棧的深度時每個遞歸調用時（I達到了這個效果通過添加附加String參數backtrack由「」在generateParenthesis並且由級聯「初始化 - 」每次遞歸發生）。

來源

2016-02-13 10:06:52

我認爲你對返回的位置以及遞歸函數中的if語句，回溯有點困惑。

遞歸函數越來越深，直到他們到達一個稱爲基本情況的案例，從中他們不能再下降。您應該注意到，每個降級都是通過調用遞歸函數來實現的。關鍵的一點是，每個調用它是一個獨立函數的調用，因此應單獨返回。

如果你直覺上，而且可悲地錯誤地認爲是正確的，那麼在達到基本情況時，你會完全終止遞歸。相反，如果你有如下的遞歸關係，並且你從函數g中調用了f（n），那麼你的遞歸將像f（n-1），f（n-2），... f（ 2），f（1），f（0）。當f（0）返回時，它不會將其值返回給g。它實際上會將它的值再次返回給函數f，它的參數是1.（即基本上遵循它在下降到f（0）時使用的方向，僅在相反時）f（1）然後返回到函數f，它的參數是2.這將繼續，直到你調用f參數爲n。只有這樣，返回值纔會返回到g。

private void f(int i){ 
    if(i == 0) { 
     return 0; 
    } 
    else { 
     return f(i-1); 
    } 
}

你心目中的第一個問題是我覺得很容易做出迴應，如果你明白我上面所說的。簡而言之，對於較低級別的遞歸調用並不意味着一旦對較低級別的調用返回，遞歸的當前級別也將被終止。如果你明白這個事實，爲了回答你的第一個問題，你需要做的就是注意到回溯函數中的分支是通過使用兩個如果函數來執行的，而不是一個如果函數的其他函數。實際上，一旦第一個（即以'（'作爲參數）回調調用到較低級別的遞歸返回，因爲遞歸的當前級別不會終止，將會運行單獨的if檢查，並且如果發現必要的話。關閉<打開）回溯將被第二次調用。（即這次用'）'和其他相關的參數）因爲這是在遞歸的每個級別完成的，所以該函數可以在添加'（'2次之後添加'）'

來源

2016-03-22 12:05:49 ilim

關於遞歸DFS的2個問題

回答

相關問題