Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

• Time: O(n)
• Space: O(1)

public List<String> generateParenthesis(int n) {
    List<String> ret = new ArrayList<String>();
    dfs(ret, n, n, "");
    return ret;
}

private void dfs(List<String> ret, int l, int r, String str) {
    if (l == 0 && r == 0) {
        ret.add(str);
    }
    if (l > 0) {
        dfs(ret, l - 1, r, str + "(");
    }
    if (l < r) {
        dfs(ret, l, r - 1, str + ")");
    }
}