Brute force tries possible answers directly. It is often the simplest correct solution before any optimization is added.
Brute force is useful because it makes the problem’s search space visible.
Core Idea
The algorithm lists candidates, checks each candidate, and returns the one that satisfies the condition. If there are many candidates, brute force can become too slow.
Even when it is not efficient enough, a brute-force solution often clarifies what a better algorithm must avoid repeating.
Brute force is a reasoning tool. It answers: “What would I do if efficiency did not matter?” That direct answer often reveals the states, choices, or repeated checks that a better solution can optimize.
Function Contract
has_pair_sum(values, target) expects a sequence of numbers and a target sum.
It returns True if two different positions add to target, and False otherwise. The nested loops intentionally check every pair, so the function is a direct baseline rather than an optimized solution.
Python Example
def has_pair_sum(values, target):
for i in range(len(values)):
for j in range(i + 1, len(values)):
if values[i] + values[j] == target:
return True
return FalseThis checks every pair. The time complexity is O(n^2).
Why It Helps Learning
For the pair-sum problem, brute force says the real question is about pairs of indexes. A hash-map solution improves the search, but it still answers the same question: whether some earlier value can pair with the current value.
Starting from brute force prevents a common mistake: reaching for a technique before understanding what candidates exist.
When It Becomes Too Slow
Candidate counts grow quickly:
- All single elements:
n. - All pairs: about
n^2. - All subsets:
2^n. - All permutations:
n!.
If the input size is large, brute force over subsets or permutations becomes impossible very quickly.
How To Improve From It
After writing a brute-force solution, look for repeated work. Repeated membership checks may suggest a set or dictionary. Repeated range calculations may suggest prefix sums. Repeated recursive states may suggest dynamic programming. Repeated invalid branches may suggest backtracking with pruning.
The brute-force version is useful because it shows exactly what the optimized version must preserve.
Common Confusions
Brute force is not automatically wrong. It may be the right answer for small constraints or a useful first version.
The mistake is keeping brute force when the input size makes the number of candidates too large.
Another mistake is calling any simple solution brute force. A direct one-pass algorithm may be simple and efficient. Brute force specifically means trying a broad set of candidates directly.
When To Use It
Use brute force to get a baseline, verify small test cases, understand the search space, or solve problems whose constraints are small enough for direct enumeration.
Then ask what repeats. Repeated scans may suggest a hash map. Repeated subproblems may suggest dynamic programming. Repeated invalid branches may suggest backtracking with pruning.
The Main Point
Brute force is the direct search of candidates. It is valuable as a correctness baseline and as a way to reveal what an optimized algorithm must avoid repeating.