iT邦幫忙

0

python backtrack的問題

    def generateParenthesis(self, n):
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return 
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
                
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()
                

本題為LeetCode第22題
請問在這個回朔法(backtrack)裡面的S.pop()是怎麼運作的,
在我的認知裡面一旦呼叫backtrack之後就不會再呼叫S.pop()了,

我看了很多外國的YT影片都沒運用到類似的技巧
所以來跟大家求救這個S.pop()到底是怎麼運作的

#本人非本科,自學菜雞求救

2 個回答

0
uobik
iT邦新手 4 級 ‧ 2021-06-29 21:29:19
最佳解答

當執行到第9行時 backtrack(S, left+1, right),
它再次呼叫backtrack,等這個新呼叫的backtrack處理完後,自然會接續第10行 S.pop()

整個過程中會呼叫很多次backtrack,可能不好想
轉換了一個中文說明的程式碼,印出運算過程,看能不能幫助到你

括號對數 = 2
次數 = 0
答案 = []

def backtrack(當前組合, 左括號數, 右括號數):
    global 次數
    次數 += 1
    print('\n呼叫第' + str(次數) + '次backtrack')
    print('當前組合=' + str(當前組合))

    if len(當前組合) == 2 * 括號對數:
        答案.append(''.join(當前組合))
        print('括號數已滿,不再填充。儲存答案' + str(答案))
        print('backtrack執行完畢(中斷)')
        return
    if 左括號數 < 括號對數:
        當前組合.append('(')
        print('填充左括號')
        backtrack(當前組合, 左括號數+1, 右括號數)
        print('上個backtrack執行完畢,此為第20行程式碼印出')
        當前組合.pop()
        print('移除最後元素')
    if 右括號數 < 左括號數:
        當前組合.append(')')
        print('填充右括號')
        backtrack(當前組合, 左括號數, 右括號數+1)
        print('上個backtrack執行完畢,此為第27行程式碼印出')
        當前組合.pop()
        print('移除最後元素')
    print('backtrack執行完畢(結尾)')

backtrack([], 0, 0)
print('\n答案為:' + str(答案))

https://ithelp.ithome.com.tw/upload/images/20210629/201389821qty8rN0yz.png

看更多先前的回應...收起先前的回應...

在呼叫

呼叫第5次Backtrack後面
"上個Backtrack執行完畢,此為第20行程式碼印出"
"移除最後元素"
"填充右括號" <<<<<<(???)

甚麼會填充右括號?

麻煩大大在幫我解惑這個問題

uobik iT邦新手 4 級 ‧ 2021-06-30 18:56:46 檢舉

就繼續往後執行,遇到第三個if判斷,有符合(右括號數 < 左括號數),所以填充右括號

感謝大大

不好意思那照你這麼說得這樣的話

"就繼續往後執行,遇到第三個if判斷,有符合(右括號數 < 左括號數),所以填充右括號"

會先遇到 左括號數 < 括號對數 不是嗎?
怎麼直接略過第二個if 直接到第三個if

uobik iT邦新手 4 級 ‧ 2021-07-01 16:20:34 檢舉

它沒有略過第二個if,第二個if在前面已經執行完了,
而第三個if也符合執行條件,所以繼續接著執行

每個backtrack,除非遇到return中斷,不然都是有完整跑一遍,執行到底的

0
小魚
iT邦大師 1 級 ‧ 2021-06-29 18:27:59

沒看到實際帶入的數字,
不過說這句話的理由是甚麼?

一旦呼叫backtrack之後就不會再呼叫S.pop()了

我要發表回答

立即登入回答