값 n이 있다고 가정합니다. n개의 여는 괄호와 닫는 괄호가 있는 모든 가능한 잘 구성된 괄호를 생성해야 합니다. 따라서 n =3의 값이면 괄호 세트는 ["()()()","()(())","(())()","(()()) ","((()))"]
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- genParenthesisRec()라는 메서드를 정의합니다. 이것은 왼쪽, 오른쪽, 임시 문자열 및 결과 배열을 사용합니다. 초기 결과 배열이 비어 있습니다.
- genParenthesisRec 함수는 아래와 같이 작동합니다.
- left =0이고 right :=0이면 결과에 temp를 삽입하고 반환합니다.
- 남은 경우> 0
- getParenthesisRec(왼쪽 – 1, 오른쪽, 온도 + "(", 결과)
- 오른쪽> 왼쪽
- getParenthesisRec(왼쪽, 오른쪽 – 1, 온도 + ")", 결과)
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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)) 입력
4
출력
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]