How to Choose Between Brute Force, Greedy, and Dynamic Programming

Every coding problem quietly asks the same thing when you choose between brute force, greedy, and DP: which technique do you pull out of the toolbox? This post outlines the decision process for the specific signals in a problem statement that point to brute force, greedy, divide and conquer, dynamic programming, backtracking, or branch and bound within the first 60 seconds of reading.

What question does each technique actually answer?

Each technique is the optimal answer to one structural question about your problem, not an interchangeable “style.” Match the question the problem is really asking, and the technique follows. Keep this table in mind; everything below expands on it.

Fig 1: A decision guide for selecting the right algorithm design technique.

When should you use brute force?

Use brute force when the input is small (n ≤ 20), or you need a correctness baseline before optimizing. It tries every possible solution and keeps the best or first valid one- slow, but never wrong

When to use it

• The input size is small (n ≤ 20, or explicitly bounded in the problem).
• You need a correctness baseline before optimizing brute-force methods, which is how you verify that a smarter solution is actually right.
• No clean structure (no greedy-choice property, no optimal substructure) is apparent, and you’re out of time to find one.
• The problem says things like “n ≤ 10” or “count all subsets/permutations,” which are brute-force flags.

When to avoid it

• Input size exceeds ~10⁶, or exponential blowup is likely (n > 25 for subsets, n > 10 for permutations).

Rule of thumb: always mentally solve the brute-force version first, even if you won’t submit it, it reveals the structure that tells you whether greedy, DP, or backtracking applies next.

When does a greedy algorithm actually work?

Greedy works only when a locally optimal choice at each step provably leads to a globally optimal solution, the greedy-choice property. If you can’t prove that don’t trust it.

When to use it

• The problem has the greedy-choice property. Classic examples: activity selection, Huffman coding, minimum spanning tree (Kruskal’s/Prim’s), and coin change with standard currency.
• The problem has optimal substructure, but choices don’t need to be reconsidered later.
• Sorting the input by some criterion (deadline, ratio, size) and scanning once solves it.

How to know it’s not greedy

 Counterexample: coin change with denominations {1, 3, 4} and a target of 6; greedy picks 4+1+1 for three coins, but 3+3 is optimal with two coins.

If the problem asks for a globally optimal count or value but the choices interact, that’s usually a DP signal instead. Rule of thumb: if you can’t prove, even informally, via an exchange argument, that the greedy choice never needs undoing, test it against small adversarial cases before committing.

When should you use divide and conquer?

Use divide-and-conquer when a problem can be split into subproblems that don’t depend on each other’s answers. Solve each recursively, then combine the results. This is the key difference from dynamic programming.

When to use it

• Subproblems are independent; solving one doesn’t depend on the answer to another.
• There’s a natural split point: sorting (merge sort, quicksort), searching (binary search), or matrix multiplication (Strassen’s).
• You can express a recurrence like T(n) = a·T(n/b) + f(n), and the combine step is cheap relative to the split.

Avoid it when subproblems overlap significantly; you’ll redo the same work repeatedly, which is your cue to move to DP instead. Rule of thumb: D&C shines when the “combine” step is straightforward, like merging two sorted arrays. If combining is as hard as the original problem, D&C isn’t buying you much.

How do you know a problem needs dynamic programming?

• A problem needs dynamic programming when subproblems overlap; the same smaller subproblem gets solved repeatedly inside a brute-force recursion, and it asks for an optimal value or count rather than a full list of solutions.

How to spot it fast

• The problem asks for an optimal value (max/min/count of ways) rather than “list all solutions,” which is a strong DP signal.
• You can define a recurrence where a bigger problem’s answer depends on smaller versions of the same problem, e.g., fib(n) = fib(n-1) + fib(n-2).
• Draw the brute-force recursion tree: if the same subproblem gets solved multiple times, that duplication is exactly what DP eliminates.
• Classic families: knapsack, longest common subsequence, edit distance, and coin change.

Two flavors solve it: top-down memoization (write the brute-force recursion, add a cache) and bottom-up tabulation (build a table iteratively from base cases up, usually more space-efficient and avoids recursion-depth limits).

Rule of thumb: if you catch yourself writing a brute-force recursive solution and thinking “I keep computing f(3, 7) over and over,” you’ve already found your DP state, just add memoization. MIT’s introductory algorithms course frames this well: DP is “careful, exhaustive search” with reuse, not a separate universe of technique.

How do these techniques compare on the same problem?

Take the 0/1 Knapsack problem: choose items to maximize value while staying within a weight limit. All four techniques apply to it, and which one wins depends entirely on the input’s size and shape.

• Brute force: try all 2ⁿ subsets, correct, but exponential.
• Greedy: sort by value-to-weight ratio and take greedily, this fails in general once integrality constraints kick in (capacity 50 with items (60,10), (100,20), (120,30) is a working counterexample).
• Dynamic programming: define dp[i][w] as the best value using the first i items with capacity w. Subproblems overlap heavily, so DP is the right fit, running in O(n·W).
• Backtracking with bounding (branch and bound): useful when weights are huge or fractional, making the DP table too large, bound each branch by the fractional-knapsack upper bound, and prune.

Choosing the Right Algorithm

Choosing among Brute Force, Greedy, Divide and Conquer, Dynamic Programming, Backtracking, and Branch and Bound depends on the problem’s structure. Start by understanding the simplest brute-force solution, then look for greedy-choice properties, independent subproblems, overlapping subproblems, or opportunities to prune the search space. The key is not to choose a technique based on popularity, but to identify the pattern that best matches the problem.