Backtracking

Technique that explores possible solutions and backtracks when a path is invalid.

N-Queens

Place N queens on a chessboard so that none attack each other.

Time: O(N!)

Space: O(N)

Knight's Tour

Move a knight so it visits every square of the board once.

Time: O(8^(N²))

Space: O(N²)

Permutations

Generate all possible orderings of a set of elements.

Time: O(N!)

Space: O(N)

Generate Parentheses

Generate Parentheses is a classic backtracking problem where the goal is to generate all possible combinations of well-formed parentheses for a given number n. The algorithm builds the string step by step and ensures validity by never allowing the number of closing parentheses to exceed the number of opening ones. This constraint prunes invalid branches early and makes the search efficient.

Time: O(4^n / sqrt(n))

Space: O(n)