[LeetCode]GenerateParentheses

Gernerateparenttheses

접근 방법 (fail)

괄호를 열었다 닫았다 하는 경우의 수를 계산해보았다. 단순하게 DP했던것처럼 3가지 경우의 수가 나왔다.

앞에 붙히는 방식, 뒤에 붙히는 방식, 양 옆에 붙히는 방식 하지만 n= 4일때부터는 원하는대로 동작하지 않아서 실패하였다.
실패한 경우 = "(())(())"

    // sovle HashSet adding
    solve("()"+str,deps-1);
    solve(str+"()", deps-1);
    solve("("+str+")", deps-1);

접근 방법(success)

괄호 한짝을 추가해주는것이 아니라. 하나씩을 backtracking 기법으로 다루기로 생각하였고

그리고 추가하는 조건의 두가지의 조건이 나왔다.
"(" 의 수가 n을 넘어가지 않아야한다. 그러면 "("을 추가할 수 있다.
")" 는 "(" 의 수보다 적어야지 추가할 수 있다.

그리고 기저사례로는 "(" 와 ")"의 수가 둘다 n 이어야한다.

구현

    public static void solve(List<String> res, String str, int openDeps, int closeDeps) {
        if (openDeps == 0 && closeDeps == 0)
            res.add(str);
        if (openDeps > 0)
            solve(res, str + "(", openDeps - 1, closeDeps);
        if (openDeps < closeDeps)
            solve(res, str + ")", openDeps, closeDeps - 1);
    }

읽어주셔서 감사합니다.