Tạo ngoặc hợp lệ (Generate Parentheses) trong Python

Giả sử chúng ta có một giá trị n. Chúng ta phải tạo tất cả các chuỗi ngoặc hợp lệ (well-formed parentheses) có n cặp ngoặc mở và đóng. Ví dụ, nếu n = 3, tập ngoặc sẽ là ["()()()","()(())","(())()","(()())","((()))"].

Để giải quyết, chúng ta làm theo các bước sau:

Định nghĩa phương thức genParenthesisRec(). Nó nhận left, right, chuỗi tạm temp và mảng kết quả result. Ban đầu result rỗng.
Hàm genParenthesisRec hoạt động như sau:
- Nếu left == 0 và right == 0, chèn temp vào result, và trả về.
- Nếu left > 0:
  - Gọi genParenthesisRec(left - 1, right, temp + "(", result).
- Nếu right > left:
  - Gọi genParenthesisRec(left, right - 1, temp + ")", result).

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

Đầu ra

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