N Queens: the idea to remember.

The core insight

Place one queen per row while tracking occupied columns and both diagonal identifiers.

Why it works

One queen per row handles row conflicts; equal column, row minus column, or row plus column identifiers detect all other attacks.

The mistake to avoid

Undo all three occupied markers after exploring a placement so sibling branches remain independent.

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.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Place one queen per row while tracking occupied columns and both diagonal identifiers.
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    List<String> cur = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    Set<Integer> leftSet = new HashSet<>(); 
    Set<Integer> rightSet = new HashSet<>(); 
    Set<Integer> colSet = new HashSet<>(); 
    dfs(n, result, cur, leftSet, rightSet, colSet);
    return result;
}

private void dfs(int n, List<List<String>> result, List<String> cur, Set<Integer> leftSet,
        Set<Integer> rightSet, Set<Integer> colSet) {
    if (cur.size() == n) {
        result.add(new ArrayList(cur));
        return;
    }
    int row = cur.size();

    for (int i = 0; i < n; i++) {
        if (leftSet.contains(row - i) || rightSet.contains(row + i) || colSet.contains(i)) {
            continue;
        }

        cur.add(convert(n, i));
        leftSet.add(row - i);
        rightSet.add(row + i);
        colSet.add(i);

        dfs(n, result, cur, leftSet, rightSet, colSet);

        cur.remove(cur.size() - 1);
        leftSet.remove(row - i);
        rightSet.remove(row + i);
        colSet.remove(i);

    }
}

private String convert(int n, int col) {
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < n; i++) {
        if (i == col) {
            res.append("Q");
        } else {
            res.append(".");
        }
    }
    return res.toString();
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection