[Question] 3. n개의 괄호 조합 구하기

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다.

정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 만들 수 있는 괄호 조합을 모두 구하라.

예제}

Input : 1

Output : ["()"]

Input : 2

Output : ["(())", "()()"]

Input : 3

Output : ["((()))", "(())()", "()(())", "()()()"]

주로 조합을 구하거나 답의 양이 많을 경우는 재귀함수를 사용하면 된다.

empty string 부터 시작하여 "("를 더하고 재귀함수를 부르고, ")"를 더하고 재귀함수를 부르면 된다.

여기서 중요한 건, 현재 몇 개의 여는 괄호를 사용 하였는지와 몇 개의 닫는 괄호를 사용 하였는지 알아야 한다.

괄호 조합을 왼쪽에서 오른쪽으로 읽을 때, 닫는 괄호가 여는 괄호 개수보다 많으면 정당한 조합이 될 수 없다.

그러므로, 재귀함수에서 여는 괄호가 n보다 작을 때 여는 괄호를 더한 재귀함수를 만들고,

닫는 괄호 개수가 여는 괄호 개수보다 작을 때 닫는 괄호를 더한 재귀함수를 만들면 된다.

재귀함수에 주어진 문자열이 (n*2) 길이를 가진다면 알맞는 괄호 조합이니, 리스트에 더해주면 된다.

List<string> parenthesisPairs(int n) {
    List<string> ans = new ArrayList();
    recurse(ans, "", 0, 0, n);
    return ans;
}

void recurse(List<string> ans, String cur, int open, int close, int n){
    if (str.length() == n * 2) {
      ans.add(cur);
      return;
  }
    if (open < n) {
      recurse(ans, cur + "(", open + 1, close, n);
    }
    if (close < open) {
      recurse(ans, cur + ")", open, close + 1, n);
    }
}