0902.2024.Today I Learned

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

Answer

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> answer = new ArrayList<String>();
        dfs(answer, 0, 0, "", n);

        return answer;
    }

    public void dfs (List<String> answer, int left, int right, String s, int n) {
        if (s.length() == n*2) {
            answer.add(s);
            return;
        }
        
        if (left < n) {
            dfs(answer, left+1, right, s+"(", n);
        }
        if (right < left) {
            dfs(answer, left, right+1, s+")", n);
        }
    }
}_텍스트_```