Practice Problems

Backtracking problems look different on the surface, but once you decide what counts as one step and when to prune, most of them fit the same template. Try the four problems below on your own first, then compare your approach with the one given.

Problem 1: balanced parentheses

Given an integer n, list every valid string made of n opening and n closing parentheses. For n = 2 the answer is (()) and ()().

Approach: append one character at a time. An opening parenthesis is allowed only while fewer than n have been used, and a closing one only while fewer have been closed than opened. These two rules are the pruning that prevents invalid strings from ever being built.

def parentheses(n):
    out = []

    def dfs(s, opened, closed):
        if len(s) == 2 * n:
            out.append(s)
            return
        if opened < n:
            dfs(s + "(", opened + 1, closed)
        if closed < opened:
            dfs(s + ")", opened, closed + 1)

    dfs("", 0, 0)
    return out

print(parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

Problem 2: find a word in a grid

You are given a 2D grid of letters and a word. Decide whether the word can be spelled by moving between horizontally or vertically adjacent cells, using each cell at most once.

Approach: start a search from every cell. Mark the current cell as in use by overwriting it with # (choose), look for the next letter in four directions (explore), then restore the original letter (unchoose). Return immediately when a letter does not match.

def exists(grid, word):
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[i]:
            return False
        saved, grid[r][c] = grid[r][c], "#"
        found = any(dfs(r + dr, c + dc, i + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        grid[r][c] = saved
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

board = [list("CAT"), list("OXD"), list("DEN")]
print(exists(board, "CODE"), exists(board, "COAT"))  # True False

Problem 3: permutations with duplicates

List the distinct permutations of a list that contains repeated values, such as [1, 1, 2]. No permutation may appear twice in the output.

Approach: sort first. Picking the same value twice at the same depth repeats an identical branch, so skip a value when the equal value right before it has not been used yet. This shrinks the search itself, which is better than generating duplicates and removing them with a set.