[백트래킹] LC #22 Generate Parentheses

문제 설명

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:


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

1. 백트래킹(Backtracking)이란 무엇일까?

가장 직관적으로 이해하자면, 백트래킹은 미로 찾기를 할 때 "이 길이 아닌가 보네? 다시 뒤로 돌아가서 다른 길로 가야지" 하는 행동을 알고리즘으로 만든 것입니다.

핵심 개념: 모든 가능한 경우의 수를 탐색하되, 어떤 조건을 만족하지 않는 경로라면 더 이상 깊이 들어가지 않고(가지치기), 직전 상태로 되돌아와서(Back) 다른 경로를 탐색하는(Tracking) 알고리즘 기법입니다.

무식하게 다 해보기 (Brute Force) vs. 백트래킹 (Backtracking)

2. LeetCode 22번 (괄호 만들기)가 왜 백트래킹일까?

이 문제에서 n=3일 때, 유효한 괄호 쌍(예: ((())), ()()())을 만들어야 합니다. 컴퓨터가 빈 문자열 ""에서 시작해서 괄호를 하나씩 붙여나가는 과정을 미로 찾기라고 생각해볼 수 있습니다.

🚫 백트래킹이 없다면? (무식한 방법)

여는 괄호 (와 닫는 괄호 )를 무조건 6개 채울 때까지 모든 조합을 만듭니다. ((((((, )))))), ()()(), )))( (( 등을 다 만든 뒤, 마지막에 가서야 "어? )))( ((는 올바른 괄호가 아니네?" 하고 버립니다. 엄청난 시간 낭비가 발생합니다.

✨ 백트래킹을 적용하면?

괄호를 붙여나가는 와중에 "어차피 끝까지 가봤자 정답이 될 수 없는 상태"를 미리 감지하고 돌아섭니다. (가지치기)

3. Java 코드 구현 (정석적인 백트래킹)

재귀를 활용한 깔끔한 백트래킹 구조입니다. 전역 변수 대신 매개변수로 상태를 넘겨주어 각 재귀 호출이 독립적으로 상태를 관리하도록 합니다. 

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // 시작 상태: 빈 문자열 "", 여는 괄호 0개, 닫는 괄호 0개
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String currentString, int openCount, int closeCount, int max) {
        // [1] 탈출 조건: 원하는 길이(2 * n)에 도달하면 정답 리스트에 추가하고 종료
        if (currentString.length() == max * 2) {
            result.add(currentString);
            return;
        }

        // [2] 여는 괄호 추가 (가지치기 조건 포함)
        if (openCount < max) {
            backtrack(result, currentString + "(", openCount + 1, closeCount, max);
        }

        // [3] 닫는 괄호 추가 (가지치기 조건 포함)
        if (closeCount < openCount) {
            backtrack(result, currentString + ")", openCount, closeCount + 1, max);
        }
    }
}

💡 코드 세부 포인트