Java easy to understand recursive solution.


  • 0
    C
    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        dfs(n, n, "", ret);
        return ret;
    }
    
    // l, r means how many "(" and ")" left respectively
    private void dfs(int l, int r, String path, List<String> ret) {
        if (l <= r) {
            if (l == 0 && r == 0) { 
                ret.add(path);
                return;  // backtracking
            }
            if (l < 0 || r < 0) {
                return;  // backtracking
            }
            dfs(l-1, r, path+"(", ret);
            dfs(l, r-1, path+")", ret);
        }
    }

Log in to reply
 

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