Giả sử chúng ta có giá trị n. Chúng ta phải tạo ra tất cả các dấu ngoặc đơn có thể có trong đó có n số lượng dấu ngoặc mở và đóng. Vì vậy, nếu giá trị của n =3, thì bộ dấu ngoặc sẽ là ["() () ()", "() (())", "(()) ()", "(() ()) "," ((())) "]
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
- Định nghĩa phương thức được gọi là genParenthesisRec (). Điều này lấy trái, phải, chuỗi tạm thời và mảng kết quả. mảng kết quả ban đầu trống
- Hàm genParenthesisRec, sẽ hoạt động như bên dưới
- nếu left =0 và right:=0, sau đó chèn tạm thời vào kết quả và trả về
- nếu trái> 0
- getParenthesisRec (left - 1, right, temp + “(”, result)
- nếu phải> trái
- getParenthesisRec (left, right - 1, temp + “)”, result)
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
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
4
Đầu ra
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]