값 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
출력
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]