Introduction

Greedy algorithms and exhaustive search both try to solve decision or optimization problems, but they do so with very different attitudes toward the search space. A greedy algorithm commits to the best-looking local choice at each step, while exhaustive search systematically considers every possible complete solution before deciding which one is best.

Greedy Means Commit Early

A greedy algorithm makes a choice that looks best right now and never revisits it. That can be very fast when the problem has the right mathematical structure.

A classic example is interval scheduling: choose the next activity that finishes earliest.

1def select_intervals(intervals):
2    intervals = sorted(intervals, key=lambda x: x[1])
3    result = []
4    current_end = float('-inf')
5
6    for start, end in intervals:
7        if start >= current_end:
8            result.append((start, end))
9            current_end = end
10
11    return result
12
13print(select_intervals([(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]))

The algorithm does not test every subset of intervals. It keeps making locally optimal choices and relies on the problem's greedy property.

Exhaustive Search Means Explore Everything

Exhaustive search does not trust local choices. It enumerates all possible complete candidates and then picks the valid or optimal one.

1from itertools import combinations
2
3
4def best_subset(nums, limit):
5    best = []
6    for r in range(len(nums) + 1):
7        for candidate in combinations(nums, r):
8            if sum(candidate) <= limit and sum(candidate) > sum(best):
9                best = list(candidate)
10    return best
11
12print(best_subset([2, 5, 6, 9], 11))

This approach is much more expensive, but it is complete: if a solution exists in the search space, exhaustive search will find it.

The Tradeoff: Speed Versus Certainty

The central difference is the tradeoff being made.

• greedy search is usually much faster
• exhaustive search is usually much more expensive
• greedy search may miss the global optimum
• exhaustive search guarantees the global optimum if you search the whole space

That is why greedy methods are attractive but only safe on problems where a local choice really does lead toward a globally optimal answer.

Greedy Is Not Just "Faster Brute Force"

It is tempting to think of greedy algorithms as optimized exhaustive search, but that is not what they are doing. Exhaustive search keeps alternatives alive until it has enough information to compare them. Greedy methods discard alternatives immediately.

That difference in commitment is what makes greedy algorithms elegant on the right problems and dangerously wrong on the wrong ones.

Example Where Greedy Can Fail

Coin change is a useful warning example. A greedy algorithm that takes the largest coin first works for some coin systems, but not for all.

1def greedy_change(coins, amount):
2    result = []
3    for coin in sorted(coins, reverse=True):
4        while amount >= coin:
5            amount -= coin
6            result.append(coin)
7    return result
8
9print(greedy_change([1, 3, 4], 6))

This returns [4, 1, 1], but the optimal solution is [3, 3]. Exhaustive search would eventually find the true optimum because it checks all possibilities.

When to Choose Which

Choose a greedy approach when:

• the problem is known to satisfy the greedy-choice property
• you need speed and simplicity
• the optimal solution can be proven from local decisions

Choose exhaustive search when:

• correctness must be guaranteed
• the search space is small enough to explore fully
• the problem lacks a trustworthy greedy rule

In real systems, exhaustive search is often used for verification on small instances even when a faster heuristic is used in production.

Common Pitfalls

A common mistake is calling an algorithm greedy just because it is fast. A real greedy algorithm makes irrevocable local decisions.

Another is assuming that because a greedy method works on a few examples, it must be correct in general. Without a proof or a known theorem, that assumption is risky.

Developers also sometimes choose exhaustive search without checking how quickly the search space grows. Completeness is useful only if the runtime is still practical.

Summary

• Greedy algorithms choose the best-looking local step and commit immediately.
• Exhaustive search evaluates every possible complete solution.
• Greedy methods are often much faster but may fail to find the global optimum.
• Exhaustive search is slower but guarantees completeness.
• The right choice depends on whether the problem has a valid greedy structure and whether full search is affordable.