[leetcode 22] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

n개의 올바른 괄호로 구성된 문자열 만들기

 

Example 1:

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

Example 2:

Input: n = 1 Output: ["()"]

 

풀이:

-백트래킹 문제

-비교적 쉬웠다.

class Solution {
public:
    vector<string> answer;
    int N;
    
    void BackTracking(int front, int back, string tmp){
        if(front == N && back == N){
            answer.push_back(tmp);
            return;
        }
        
        if(front < N){
            BackTracking(front+1, back, tmp+"("); 
        }
       
        if(front > back){
          BackTracking(front, back+1, tmp+")");
        }
    }
    
    vector<string> generateParenthesis(int n) {
       N=n;
        BackTracking(0,0,"");
        return answer;
    }
};