Generate Parentheses ใน Python - สร้างวงเล็บที่ถูกต้องทั้งหมด

สมมติว่าเรามีค่า n เราต้องสร้าง parentheses ที่ well-formed ทั้งหมดที่มีวงเล็บเปิดและปิด n คู่ ตัวอย่าง n = 3 ผลลัพธ์คือ ["()()()","()(())","(())()","(()())","((()))"]

ขั้นตอนการทำงาน (Recursive Backtracking)

1. กำหนดเมธอด genParenthesisRec() รับ left, right, temp string, result array เริ่มต้น result ว่าง
2. ฟังก์ชันทำงานดังนี้:
   • ถ้า left = 0 and right = 0 ใส่ temp ลง result คืนค่า
   • ถ้า 0: เรียก genParenthesisRec(left-1, right, temp + "(", result)
   • ถ้า right > left: เรียก genParenthesisRec(left, right-1, temp + ")", result)

ตัวอย่างโค้ด (Python)

class Solution(object):
    def generateParenthesis(self, n):
        result = []
        self.generateParenthesisUtil(n, n, "", result)
        return result

    def generateParenthesisUtil(self, left, right, temp, result):
        if left == 0 and right == 0:
            result.append(temp)
            return
        if left > 0:
            self.generateParenthesisUtil(left-1, right, temp+'(', result)
        if right > left:
            self.generateParenthesisUtil(left, right-1, temp+')', result)

ob = Solution()
print(ob.generateParenthesis(4))

อินพุต

4

เอาต์พุต

["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]