Implementation

This chapter implements subsets, permutations, and N-Queens in Python and walks through them line by line. Then it ports the same core routine, counting N-Queens solutions, to C++, Java, and TypeScript. Whatever the language, the structure is the same three lines: choose, explore, unchoose.

Subsets and permutations (Python)

def subsets(nums):
    result, path = [], []

    def dfs(start):
        result.append(path[:])            # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            dfs(i + 1)                    # explore: only pick after i
            path.pop()                    # unchoose

    dfs(0)
    return result


def permutations(nums):
    result, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):        # leaf: one full permutation
            result.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:                   # skip elements already taken
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

• subsets records a result at every node, not just at leaves. Because it only picks from start onward, [1, 2] and [2, 1] are never both produced.
• permutations cares about order, so it scans from the beginning every time and uses the used array to block elements already chosen. used[i] = False is the matching undo.
• Both functions store a copy with path[:].

N-Queens (Python)

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    queens, boards = [], []

    def place(row):
        if row == n:                                   # every row filled
            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                               # prune
            cols.add(c); diag.add(row - c); anti.add(row + c)
            queens.append(c)
            place(row + 1)
            queens.pop()
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return boards

for line in solve_n_queens(4)[0]:
    print(line)
# .Q..
# ...Q
# Q...
# ..Q.

• One queen goes in each row, so row is the depth of the tree.
• Three sets, cols, diag (row - c), and anti (row + c), make each conflict check O(1). Scanning every queen, as is_safe did in the previous chapter, costs per check.