How different computational problems relate to one another, why Enumeration is the foundation of all of them, and why we use smart algorithmic paradigms instead of checking every possibility by hand.
Think of any problem as a two-stage journey: first, you filter out all the impossible choices to create a list of valid possibilities (Enumeration). Once you have that list, the problem type simply depends on what question you ask about it.
Every theoretical combination of items. Many of these break the rules (e.g., exceeding the maximum bag weight).
The complete collection of choices that follow every rule. Every other problem type is just an operation done on this single list:
"Just hand me any valid solution."
Stops immediately as soon as 1 satisfying item is found.
"Is there at least one valid solution?"
Answers strictly YES or NO.
"How many valid choices are there?"
Tallies the total without needing to store each item.
"Which one of these has the highest score?"
Compares all valid items and keeps the winner.
Suppose you are packing a bag. Your bag can hold a maximum weight of 5 kg. You have 4 items to choose from:
If you can solve every problem by generating the full list and inspecting it, why do we need algorithm paradigms?
With 4 items, there are only 16 choices. But with 50 items, there are over 1,000,000,000,000,000 candidate choices. Listing them all would take thousands of years.
Algorithmic paradigms are shortcuts that answer Decision, Search, Counting, or Optimization questions without ever generating the whole list.
| Paradigm | How It Avoids the Full List | What It Solves Best |
|---|---|---|
| Brute Force | Does not avoid it. Exhaustively visits every single choice one by one. | Small toy problems |
| Backtracking | Builds solutions step-by-step. The moment a rule is broken (e.g., bag exceeds 5 kg), it stops and turns back immediately, ignoring that entire branch. | Search • Decision • Enumeration |
| Branch & Bound | Tracks the best score found so far. If an incomplete branch cannot mathematically beat the record, it abandons the branch immediately. | Optimization |
| Dynamic Programming | Notices when two different paths lead to the same situation (e.g., "3 kg remaining"). It solves that subproblem once, saves the result, and reuses it. | Optimization • Counting |
| Greedy | Never branches or reconsiders. It makes the single most attractive immediate choice at each step and moves forward. | Fast Approximate Optimization |
| Divide & Conquer | Splits the problem into independent, disjoint sub-problems, solves each half, and combines the results. | Counting • Math Evaluation |
A high-level summary showing which algorithmic paradigm natively fits each problem type, which ones are feasible but slow, and which ones are not applicable.
| Paradigm | Search | Enumeration | Optimization | Counting | Decision |
|---|---|---|---|---|---|
| Brute-Force | Feasible | Native Fit | Inefficient | Feasible | Feasible |
| Backtracking | Native Fit | Native Fit | Inefficient | Native Fit | Native Fit |
| Greedy | Feasible | Inapplicable | Native Fit | Inapplicable | Feasible |
| Divide & Conquer | Native Fit | Inefficient | Native Fit | Native Fit | Native Fit |
| Dynamic Programming | Feasible | Inefficient | Native Fit | Native Fit | Native Fit |
| Branch & Bound | Inefficient | Inapplicable | Native Fit | Inapplicable | Inefficient |