[LeetCode 22] Generate Parentheses with Java

https://leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

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

import java.util.*;

public class Solution {
    static List<String> ans;
    static StringBuilder sb;
    public List<String> generateParenthesis(int n) {
        sb = new StringBuilder();
        ans = new LinkedList<>();
        dfs(0, 0, 0, n);
        return ans;
    }
    public void dfs(int depth, int openCnt, int closeCnt, int n){
        if (depth == 2*n) {
            ans.add(sb.toString());
            return;
        }
        if (openCnt < n){
            sb.append('(');
            dfs(depth + 1, openCnt + 1, closeCnt, n);
            sb.setLength(sb.length() - 1);
        }
        if (closeCnt < openCnt){
            sb.append(')');
            dfs(depth + 1, openCnt, closeCnt + 1, n);
            sb.setLength(sb.length() - 1);
        }
    }
}

1. 어려웠던 점:

- X

 

2. 알게된 점:

- 백트래킹 복습

3. 알고리즘 풀이:

- 열린 괄호는 n의 수만큼 나올 수 있다.

그래서 if (openCnt < n)

- 닫힌 괄호는 열린 괄호의 수만큼 나올 수 있다.

그래서 if (closeCnt < openCnt)

- 2*n이 되면 n개의 괄호 쌍이 완성된다.

그래서 If (depth == 2*n)