HardNeetCode150ArrayBacktracking
N-Queens
Return all distinct solutions to N-Queens.
Examples
Input
n = 4
Output
2 solutions.
Two distinct arrangements.
Constraints
- •
1 <= n <= 9
Approaches
Try every position.
CodeT: O(n!) | S: O(n^2)
Track columns and diagonals.
CodeT: O(n!) | S: O(n)
Use bitmasks.
CodeT: O(n!) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Backtracking Brute | O(n!) | O(n^2) | Try every position. |
| Backtracking Optimized | O(n!) | O(n) | Track columns and diagonals. |
| Backtracking Bitwise | O(n!) | O(n) | Use bitmasks. |
Backtracking Brute
T: O(n!)S: O(n^2)
Try every position.
Backtracking Optimized
T: O(n!)S: O(n)
Track columns and diagonals.
Backtracking Bitwise
T: O(n!)S: O(n)
Use bitmasks.
Common Mistakes
Not checking diagonals
Wrong row/column marking
Not resetting state on backtrack