[LeetCode] 22. Generate Parentheses

Problem

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

Solution

Approach

1. 리스트에 추가되는 문자열을 만들어 나갈 때, 여는 괄호의 개수는 n의 절반을 넘기면 안되고, 닫는 괄호는 현재까지 만들어진 문자열에서 여는 괄호의 개수보다 많으면 안된다.

2. 여는 괄호와 닫는 괄호의 개수를 카운트 하며 반복을 통해 문자열을 완성하고, 완성된 문자열을 리스트에 추가한다.

3. 리스트를 반환한다.

Algorithm