(Leet Code JS)Generate Parentheses

22. Generate Parentheses

Medium

10118403Add to ListShare

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 8

 

n개의 괄호의 쌍이 잘 이루어져 있는 경우를 모두 구한 뒤,

Set() 객체를 이용해 중복을 제거한 뒤 배열을 리턴하면 된다.

 

여는 괄호의 개수 = left

닫는 괄호의 개수 = right

 

괄호는 닫는 괄호로 시작할 수 없기 때문에 처음에는 "("로 시작을 한다.

 

dfs 함수를 실행하면서 조건을 확인한다.

우선 현재 여는 괄호나 닫는 괄호의 개수가 n개를 넘으면 종료한다.

그렇지 않고 두 수가 모두 n개라면 answer 배열에 넣은 후 종료.

 

위의 경우가 아닌 경우 괄호를 추가할 수 있다는 것이다.

그렇다면 현재 string 앞뒤에 여는 괄호를 추가해 주도록 한다.

또한, right < left라면 string 맨 뒤에 닫는 괄호를 추가해 탐색을 진행한다.

 

이렇게 하면 자동으로 모든 괄호의 쌍을 answer에 저장하게 되며,

모든 탐색이 끝나면 리턴할 때 배열로 바꿔주면 중복없이 답을 찾을 수 있다.

 

 

const dfs = (n, left, right, string, answer) => {
    if(left > n || right > n){
        return;
    } else if(left === n && right === n){
        answer.add(string);
        return;
    }
    
    dfs(n, left + 1, right, string + "(", answer);
    dfs(n, left + 1, right, "(" + string, answer);
    
    if(right < left){
        dfs(n, left, right + 1, string + ")", answer);
    }
}

const generateParenthesis = (n) => {
    const answer = new Set();
    
    dfs(n, 1, 0, "(", answer);
    
    return [...answer];
};