---

📘 Exhaustive Search

(Basic Algorithm Design Technique)

1️⃣ Introduction

Exhaustive Search (also called Brute Force Technique) is the simplest algorithm design strategy.

🔹 Definition

It involves:

Trying all possible solutions and selecting the one that satisfies the problem constraints.

✔ No shortcuts
✔ No assumptions
✔ Guaranteed to find correct solution

---

2️⃣ Basic Idea

• Generate all possible candidate solutions
• Test each candidate
• Select the best or valid solution

---

3️⃣ Steps in Exhaustive Search

1. Generate all possible solutions
2. Check each solution for feasibility
3. Keep track of the best solution
4. Return final result

---

4️⃣ Characteristics of Exhaustive Search

✔ Simple and straightforward
✔ Always produces optimal solution
✔ Does not require complex logic
✖ Highly inefficient for large inputs

---

5️⃣ Examples of Exhaustive Search

---

🔹 1. Linear Search

• Check each element one by one

Time Complexity: O(n)

---

🔹 2. Traveling Salesperson Problem (Brute Force)

• Check all permutations of cities

Time Complexity: O(n!)

---

🔹 3. Subset Sum Problem

• Check all subsets

Time Complexity: O(2ⁿ)

---

🔹 4. Selection Sort

• Find minimum element repeatedly

Time Complexity: O(n²)

---

6️⃣ Advantages of Exhaustive Search

✔ Easy to understand and implement
✔ Always finds the correct solution
✔ Useful for small input sizes
✔ Can be used as a baseline solution

---

7️⃣ Disadvantages of Exhaustive Search

✖ Very high time complexity
✖ Not scalable for large problems
✖ Inefficient (redundant computations)

---