Will the Guru

Problem

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

Solution

class Solution {
    private int n;
    private List<String> result = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        this.n = n;
        String str = "";
        solve(str, "(");
        return result;
    }

    private void solve(String currentString, String addString) {
        String newString = currentString + addString;
        
        if (isValid(newString)) {
            result.add(newString);
            return;
        }

        if (newString.length() < n*2) {
            solve(newString, "(");
            solve(newString, ")");
        } else {
            return;
        }
    }

    private boolean isValid(String str) {
        int strLen = str.length();
        if (strLen != n*2) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for(int i=0;i<strLen;i++) {
            char c = str.charAt(i);
            if (c == '(') {
                stack.add(c);
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

• 재귀를 사용하는 backtracking 문제!