Data Structures & Algorithms•25 min read•Advanced

Greedy & Backtracking

When local choices reach a global optimum (greedy) — and what to do when they don't (backtracking).

Greedy algorithms

A greedy algorithm makes the locally best choice at each step, hoping it leads to the global optimum. Greedy is fast (usually O(n log n) for the sort plus O(n) for the sweep) — but it only works for problems where the local-optimum property holds. Proving it does is half the work.

Classic example: activity selection

Given meetings with start and end times, select the maximum number you can attend. The greedy rule: always pick the meeting that ENDS earliest. Sort by end time, then sweep.

python

Try in Playground →

def max_meetings(intervals):
    intervals.sort(key=lambda x: x[1])    # by end time
    count, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

print(max_meetings([(1, 3), (2, 4), (3, 5), (0, 6), (5, 7)]))    # 3

When greedy fails

Greedy doesn't always work. Coin change with coins [1, 3, 4] and amount 6: greedy picks 4, then 1, then 1 — three coins. But 3 + 3 — two coins — is better. For coin change you need DP, not greedy. The lesson: greedy works for SOME coin systems (like US coins) but not all. Always sanity-check with counterexamples.

Backtracking

Backtracking is exhaustive search with pruning. You build up a candidate solution one choice at a time. When a partial solution can't possibly extend to a valid one, you back up (undo the choice) and try the next option. It's brute force, but smarter — and surprisingly fast in practice.

The template: pick a choice, recurse, undo the choice. The base case is "the candidate is complete".

All subsets

python

Try in Playground →

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path.copy())
            return
        # choice 1: include nums[i]
        path.append(nums[i])
        go(i + 1)
        path.pop()
        # choice 2: skip nums[i]
        go(i + 1)
    go(0)
    return out

print(subsets([1, 2, 3]))
# [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []]

All permutations

python

Try in Playground →

def permutations(nums):
    out = []
    def go(path, rest):
        if not rest:
            out.append(path)
            return
        for i, n in enumerate(rest):
            go(path + [n], rest[:i] + rest[i + 1:])
    go([], nums)
    return out

print(permutations([1, 2, 3]))

The famous one: N-Queens

python

Try in Playground →

def solve_n_queens(n):
    out = []
    cols, diag1, diag2 = set(), set(), set()
    def go(row, placement):
        if row == n:
            out.append(placement.copy())
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            placement.append(col)
            go(row + 1, placement)
            placement.pop()
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
    go(0, [])
    return out

print(len(solve_n_queens(8)))    # 92

← Previous

Dynamic Programming

Heaps, Tries & Union-Find