Leetcode - 22. Generate Parentheses

문제

n이 주어지면 n쌍의 올바른 괄호형태의 모든 경우의수를 리턴하라.

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

해결 O(N!)

괄호가 나열되는 모든 경우의 수 중에서 정상적인 괄호만 추출하기. parans 문자열로 next_permutation을 사용하려면 parans가 초기에 정렬된 상태여야 하기 때문에 "((()))" 가 되어야한다.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        std::string parans;
        
        parans.append(n, '(');
        parans.append(n, ')');
        
        do {
            if (is_well_formed(parans)) {
                //cout << parans << " ";
                ret.push_back(parans);
            }
        } while (std::next_permutation(parans.begin(), parans.end()));
        
        return ret;
    }
    
    bool is_well_formed(string s) {
        std::stack<char> stk;
        for (char c: s) {
            if (c == '(')
                stk.push('(');
            else if (c == ')')
                if (!stk.empty())
                    stk.pop();
        }
        if (stk.empty())
            return true;    
        else
            return false;
    }
};

해결 O(2^N)

backtracking 으로 더 효율적으로 해결. 좌우 괄호갯수가 각각 n이 될때까지 str 뒤에 괄호를 합쳐서 모든 경우의 수 탐색.

• 괄호를 오른쪽에 덧 붙이는 것만으로도 모든 경우의 수를 탐색 할 수 있다. (처음에 문자열 왼쪽 오른쪽 모두 덧붙이는 완전탐색을 해야하나? 고민했었음. 한쪽만 해도 됨)

(이부분이 이 코드의 핵심일듯!)

        if (nr_right < nr_left) 
            recur(ret, nr_left, nr_right + 1, str + ")", n);

오른쪽에 )를 덧붙일수 있는 조건은, 덧 붙이기 전 항상 왼쪽의 (갯수가 더 많아야한다. 반면 (를 를 덧붙이기 위한 조건은 n개 이하 이기만 하면된다.

시간복잡도는 한 함수에서 재귀함수가 두번호출되었으니 O(2^N)이다.

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<string> generateParenthesis(int n) {
        std::vector<string> ret;
        std::string str;
        recur(ret, 0, 0, "", n);
        return ret;
    }
    
    void recur(std::vector<string> &ret, int nr_left, int nr_right, std::string str, int n) {
        /* base case */
        if (nr_left == n && nr_right == n) {
            ret.push_back(str);
            return;
        }
        
        /* recursion */
        if (nr_left < n)
            recur(ret, nr_left + 1, nr_right, str + "(", n);
        if (nr_right < nr_left) 
            /* if you want to append ")" on right side, it is required that number of "(" is less than ")" */
            recur(ret, nr_left, nr_right + 1, str + ")", n);
    }
};

• str.append() 를 쓰면 안되는 이유 -> str 변수값이 바뀜.
  처음에 str.append("(") 를 통해 합쳐서 인자로 전달했는데, 자꾸 오답이 나와서 디버깅을 한참했다. 그 이유는 해당 함수 내에서 str이 두번쓰이기 때문이다. 첫번째 recur()함수에서 str 에 (를 append해서 전달하면 그 다음 recur()함수에서 이미 append되어버린 문자열을 가지고 전달을 한다. str 변수가 바뀌지 않도록 str + "(" 로 전달해야한다. 어이없는 실수!

        if (nr_left < n)
            recur(ret, nr_left + 1, nr_right, str.append("("), n);
        if (nr_right < nr_left) 
            recur(ret, nr_left, nr_right + 1, str.append(")"), n);