[backtracking] Generate Parentheses

Leetcode에 분류가 backtracking으로 있어서 소제목을 그렇게 붙이긴 했는데, 어느 범주에 넣어야 할지 모르겠는 문제

무튼 Parentheses문제는 이전에 stack으로 한번 풀었지만, 요 문제는 범주가 다르다

숫자가 주어지면, 그 갯수만큼 well-formed한 parentheses를 만들어야 한다.

 

 

recursion을 이용했다.

예를들어 n이 3이라면, 괄호가 총 3짝이 쓰였다는 뜻인데,

일일이 만들기에는 일일이 Loop를 도는것보다, 재귀가 더 간편할거라 생각했기 때문이다.

 

recursion 함수는 결과배열, 괄호모양, n을 args로 받는다

이때 n은 left, right로 나누어 받을것이고, 이를 recursion에 이용할때 괄호의 모양을 다르게 한다.

left와 right가 0이 될때까지 돌려서 모두 0이되면 하나의 well-formed parentheses가 만들어진 것이므로 result에 넣는다.

그리고 result를 리턴해주면 된다.