Complete Search — Brute Force

After Completing This Topic

You will be able to determine when complete search is appropriate and systematically explore all possible cases using loops, permutations, and combinations.

The Most Reliable Method

If a password consists of 4 digits, you can always find it by trying all possible combinations from 0000 to 9999. This is complete search (Brute Force, Exhaustive Search).

python

# Exhaustively search for a 4-digit numeric password
for code in range(10000):
    if check(code):
        print(f"Password: {code:04d}")
        break

10,000 possibilities. For a computer, this is almost instantaneous.

The key to complete search: "It covers all cases, so the answer is guaranteed." The guarantee of accuracy is its greatest advantage.

When to Use It

Use complete search when the number of cases is reasonably small.

text

Based on the assumption that approximately 100 million (10^8) operations are possible per second:
  n ≤ 20     → 2^20 = approximately 1 million ✅
  n ≤ 10     → 10! = approximately 3.6 million ✅
  n ≤ 8      → 8! = 40,320 ✅
  n ≤ 25~30  → 2^30 = approximately 1 billion ⚠️ Risk of exceeding the time limit

In coding tests, if the input size is small (around n ≤ 20), you should first consider complete search. Before using complex algorithms, first check if "can't we just try everything?"

Pattern 1 — Nested Loops

This is the most basic form:

python

# Find pairs of numbers that sum to the target
def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

It tries all pairs. It's O(n²) but sufficient if n is small.

Pattern 2 — Permutation

All cases where order matters:

python

from itertools import permutations

# All possible orderings of [1, 2, 3]
for p in permutations([1, 2, 3]):
    print(p)
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)

The number of permutations of n items is n!. 3! = 6, 5! = 120, 10! = 3,628,800.

python

# Find the largest number that can be formed using number cards
cards = [3, 1, 4]
max_num = 0
for p in permutations(cards):
    num = int("".join(map(str, p)))
    max_num = max(max_num, num)

print(max_num)  # 431

Pattern 3 — Combination

All cases where order doesn't matter:

python

from itertools import combinations

# All possible ways to choose 3 people from a group of 5
people = ["A", "B", "C", "D", "E"]
for team in combinations(people, 3):
    print(team)
# ('A', 'B', 'C')
# ('A', 'B', 'D')
# ('A', 'B', 'E')
# ... a total of 10 (5C3 = 10)

python

# Find the cheapest combination of 2 items from a given menu
prices = {"ramen": 3500, "kimbap": 2500, "tteokbokki": 4000, "sundae": 3000}
items = list(prices.items())

cheapest = float('inf')
best_combo = None
for combo in combinations(items, 2):
    total = combo[0][1] + combo[1][1]
    if total < cheapest:
        cheapest = total
        best_combo = (combo[0][0], combo[1][0])

print(f"{best_combo}: {cheapest} won")  # ('kimbap', 'sundae'): 5500 won

Pattern 4 — Bitmask

Problems involving subsets where each element is divided into "selected" or "not selected":

python

# The number of subsets of n items = 2^n
items = ["apple", "banana", "cherry"]
n = len(items)

for mask in range(1 << n):  # 0 to 2^n - 1
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(items[i])
    print(subset)

# []
# ['apple']
# ['banana']
# ['apple', 'banana']
# ['cherry']
# ['apple', 'cherry']
# ['banana', 'cherry']
# ['apple', 'banana', 'cherry']

1 << n is 2^n. Each bit determines whether to include that element or not.

From Complete Search to Optimization

First, use complete search to find the answer, and then optimize if performance is insufficient:

Complete Search	→	Optimization Technique
All pairs (O(n²))	→	Hash map (O(n))
All subsums	→	Two pointers, sliding window
All paths	→	DP (memoization)
Exhaustive search	→	Pruning

Coding test solving order:

First, write an accurate solution using complete search.
If it exceeds the time limit, find the pattern and optimize.
Verify that the optimized solution produces the same answer as the complete search.

Key Summary

Method	Number of Cases	Tools
Nested Loops	O(n^k)	for loop
Permutation	n!	`itertools.permutations`
Combination	nCr	`itertools.combinations`
Subset	2^n	Bitmask

Backtracking — Complete Search with Pruning

A technique in which complete search stops exploring further if it determines that "this direction cannot lead to the answer" and backtracks:

python

# N-Queens problem: Place N queens on an N×N chessboard so that they don't attack each other
def solve_nqueens(n):
    solutions = []
    
    def backtrack(queens, row):
        if row == n:
            solutions.append(queens[:])
            return
        
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)
                backtrack(queens, row + 1)
                queens.pop()  # Backtrack
    
    def is_safe(queens, row, col):
        for r, c in enumerate(queens):
            if c == col or abs(r - row) == abs(c - col):
                return False
        return True
    
    backtrack([], 0)
    return solutions

print(len(solve_nqueens(8)))  # 92 possible solutions

There are approximately 4.3 billion possible arrangements on an 8×8 chessboard, but pruning reduces the number of cases actually explored to a few thousand.

Choosing Between Recursion and Loops

python

# Recursion — Natural for tree-like exploration
def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            paths.extend(find_all_paths(graph, node, end, path))
    return paths

# Loops — Suitable for simple enumeration
for i in range(n):
    for j in range(i + 1, n):
        check(arr[i], arr[j])

Use loops when the depth is fixed, and recursion when the depth is variable. Be aware of Python's recursion depth limit (default 1000).

Sense of Time Limit

To meet the time limit (usually 1-2 seconds) in coding tests, you need to estimate the number of operations:

text

Based on Python (approximate):
  10^6 operations → ~0.1 seconds
  10^7 operations → ~1 second
  10^8 operations → ~10 seconds (time limit exceeded)

python

# n=10 → 2^10 = 1,024 → complete search possible
# n=20 → 2^20 = 1,048,576 → possible, but tight
# n=30 → 2^30 = 1,073,741,824 → time limit exceeded
# n! → n=10 is 3,628,800, n=12 is 479,001,600

n Range	Possible Complexity	Technique
≤ 10	O(n!)	Permutation complete search
≤ 20	O(2^n)	Subset/Bitmask
≤ 1,000	O(n²)	Double for loop
≤ 100,000	O(n log n)	Sorting + binary search
≤ 10,000,000	O(n)	Linear search, hash

First, determine the complexity that will pass based on the input size, and then decide whether to try complete search or optimize immediately.

Complete search is not a "brute-force" method. It is a baseline that guarantees an accurate answer, and it is also the starting point for better algorithms.

BioPlayground

Exhaustive Search — Brute Force

Complete Search — Brute Force

After Completing This Topic

The Most Reliable Method

When to Use It

Pattern 1 — Nested Loops

Pattern 2 — Permutation

Pattern 3 — Combination

Pattern 4 — Bitmask

From Complete Search to Optimization

Key Summary

Backtracking — Complete Search with Pruning

Choosing Between Recursion and Loops

Sense of Time Limit

💬 Questions & Comments