LeetCode : 22. Generate Parentheses

class Solution {
    final Character LEFT = '(';
    final Character RIGHT = ')';

    final Map<Character, Character> map = new HashMap<Character, Character>() {
        {
            put(LEFT, RIGHT);
            put(RIGHT, LEFT);
        }
    };

    List<String> asnList = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        dfs(n - 1, n, "(");
        return asnList;
    }

    private void dfs(int leftCnt, int rightCnt, String s) {
        if (leftCnt == 0 && rightCnt == 0) {
            isPalindrome(s);
            return;
        }

        if (leftCnt > 0) {
            dfs(leftCnt - 1, rightCnt, append(s, LEFT));
        }

        if (rightCnt > 0) {
            dfs(leftCnt, rightCnt - 1, append(s, RIGHT));
        }
    }

    private boolean isPalindrome(String s) {
        Stack<Character> st = new Stack<>();

        boolean isPalindrome = true;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == LEFT) {
                st.push(s.charAt(i));
            } else {
                if (st.isEmpty()) {
                    isPalindrome = false;
                    break;
                }
                Character topChar = st.pop();
                if (!topChar.equals(map.get(s.charAt(i)))) {
                    isPalindrome = false;
                    break;
                }
            }
        }

        if (st.isEmpty() && isPalindrome) {
            asnList.add(s);
            return true;
        }
        return false;
    }

    private String append(String s, Character value) {
        StringBuilder sb = new StringBuilder(s);
        sb.append(value);
        return sb.toString();
    }
}

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        recursive(res, "(", n - 1, n);
        return res;
    }
    
    public void recursive(List<String> res, String s, int open, int close) {
        if (open == 0 && close == 0) {
            res.add(s);
            return;
        }
        
        if (open > 0) {
            recursive(res, s + "(", open - 1, close);
        }
        
        if (close > open) { // [1]
            recursive(res, s + ")", open, close - 1);
        }
    }
}