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()到底是怎麼運作的
#本人非本科，自學菜雞求救
已邀請的邦友 {{ invite_list.length }}/5
當執行到第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(答案))
在呼叫
呼叫第5次Backtrack後面
"上個Backtrack執行完畢，此為第20行程式碼印出"
"移除最後元素"
"填充右括號" <<<<<<(???)
甚麼會填充右括號?
麻煩大大在幫我解惑這個問題
就繼續往後執行，遇到第三個if判斷，有符合(右括號數 < 左括號數)，所以填充右括號
iThome鐵人賽
看影片追技術