looks like there is some general way(DFS or BFS) to solve Catalan number related problem


  • 0
    Z

    Here is a dfs way which is different from comparing open and close number, this kind of formation works for other catalan number related problems as well, such as unique BST and ways to add parentheses.
    it doesn't run particularly faster though, just FYI.

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if (n == 0) {
            list.add("");
            return list;
        }
    
        for (int i = 1; i <= n; ++i) {
            for (String first : generateParenthesis(i - 1)) {
                for (String second : generateParenthesis(n - i)) {
                    list.add("(" + first + ")" + second);
                }
            }
        }
    
        return list;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.