[LeetCode] 22. Generate Parentheses [JAVA(자바)]

문제 👉 https://leetcode.com/problems/generate-parentheses/

1. 문제 (괄호 생성)

n 쌍의 괄호의 모든 조합을 생성한다.

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

2. 풀이

• 백트래킹을 이용한 풀이
  • backtracking == recursion + termination check
• termination check : ( 와 ) 의 개수가 n 일 때 종료
• recurse :
  • ( 의 개수가 n 보다 작을 때 ( 추가
  • ) 의 개수가 ( 의 개수 보다 작을 때 ) 추가

3. 코드

• 백트래킹을 이용한 풀이

class Solution {
    // numClosed > numOpen -> invalid
    void process(int n, int numOpen, int numClosed, String str, List<String> ret) {
        // termination check
        if (numOpen == n && numClosed == n) {
            ret.add(str);
            return;
        }

        // recurse netxt
        if (numOpen < n) {
            process(n, numOpen + 1, numClosed, str+"(", ret); // add open brocket    
        }
        if (numOpen > numClosed) {
            process(n, numOpen, numClosed + 1, str+")", ret); // add closed brocket   
        }        
    }

    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        process(n, 0, 0, "", ret); // recurse
        return ret;
    }

}

• 결과 :

방식	Status	Runtime	Memory	Language
해시	[Accepted]	1 ms	39 MB	Java

 

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋