Generate Parentheses: the idea to remember.

The core insight

Backtrack with open and close counts. Add an opening if open < n and a closing if close < open.

Why it works

Every prefix has at least as many openings as closings. Completed prefixes of length 2n are valid. This is a backtracking problem grouped under stack in the source sheet.

The mistake to avoid

Allowing a closing when close equals open creates an invalid prefix.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

List<String> generateParenthesis(int n) {
    List<String> out = new ArrayList<>();
    build(n, 0, 0, new StringBuilder(), out);
    return out;
}
void build(int n, int open, int close, StringBuilder path, List<String> out) {
    if (path.length() == 2 * n) { out.add(path.toString()); return; }
    if (open < n) {
        path.append('('); build(n, open + 1, close, path, out); path.deleteCharAt(path.length() - 1);
    }
    if (close < open) {
        path.append(')'); build(n, open, close + 1, path, out); path.deleteCharAt(path.length() - 1);
    }
}

Make the next connection