Introduction

Backtracking and brute-force search both explore possible solutions, which is why they are often discussed together. The real difference is that brute force tries every complete candidate blindly, while backtracking builds candidates incrementally and abandons branches as soon as it can prove they cannot lead to a valid solution.

Brute Force Means Exhaustive Enumeration

A brute-force algorithm solves a problem by checking every possible answer until it finds a valid one or proves that none exist.

1def contains_target(values, target):
2    for value in values:
3        if value == target:
4            return True
5    return False
6
7print(contains_target([3, 7, 10, 12], 10))

This is brute force in a simple form: examine candidates directly, one after another, with no attempt to shrink the search space.

For combinatorial problems, brute force often means generating every permutation, subset, assignment, or path.

1from itertools import permutations
2
3
4def has_order(values, desired):
5    for candidate in permutations(values):
6        if list(candidate) == desired:
7            return True
8    return False

That style is easy to reason about, but it becomes expensive quickly.

Backtracking Uses Partial Solutions and Pruning

Backtracking still explores possibilities, but it does not wait until the end of a candidate to decide whether the branch is useless. It checks partial progress and cuts off impossible paths early.

A standard example is generating valid subsets whose sum equals a target.

1def subset_sum(nums, target):
2    result = []
3
4    def search(index, current, total):
5        if total == target:
6            result.append(current[:])
7            return
8        if total > target or index == len(nums):
9            return
10
11        current.append(nums[index])
12        search(index + 1, current, total + nums[index])
13        current.pop()
14
15        search(index + 1, current, total)
16
17    search(0, [], 0)
18    return result
19
20print(subset_sum([2, 3, 5, 6], 8))

The pruning condition if total > target is the key backtracking idea. Once that partial path is already invalid, the algorithm stops exploring deeper choices from it.

The Search Tree Perspective

Both techniques can be viewed as traversing a search tree.

• brute force usually walks the whole tree or a fixed large portion of it
• backtracking tries to cut off subtrees as early as possible

That difference matters most when constraints are strong. The more quickly you can detect that a partial choice is hopeless, the more valuable backtracking becomes.

Example: N-Queens Style Constraint Checking

Backtracking shines on problems where partial assignments can already violate the rules.

1def solve_n_queens(n):
2    cols = set()
3    diag1 = set()
4    diag2 = set()
5    board = []
6    solutions = []
7
8    def place(row):
9        if row == n:
10            solutions.append(board[:])
11            return
12
13        for col in range(n):
14            if col in cols or row - col in diag1 or row + col in diag2:
15                continue
16
17            cols.add(col)
18            diag1.add(row - col)
19            diag2.add(row + col)
20            board.append(col)
21
22            place(row + 1)
23
24            board.pop()
25            cols.remove(col)
26            diag1.remove(row - col)
27            diag2.remove(row + col)
28
29    place(0)
30    return solutions
31
32print(len(solve_n_queens(4)))

A brute-force approach would generate far more full board arrangements before checking whether they were valid. Backtracking rejects invalid placements row by row.

Neither Technique Is Automatically Better

Brute force is sometimes the right choice when:

• the input is small
• correctness matters more than optimization
• constraints are weak or hard to exploit
• implementation simplicity is important

Backtracking is usually stronger when partial constraints can rule out large parts of the search space.

That said, backtracking is not magic. If pruning is weak, the algorithm can still approach brute-force behavior.

Common Pitfalls

A common mistake is calling every recursive search "backtracking." If the algorithm does not prune partial states, it is often just recursive brute force.

Another is assuming backtracking always changes worst-case complexity dramatically. In many hard problems, the worst case is still exponential.

Developers also sometimes add pruning conditions that are incorrect, which turns a valid backtracking algorithm into one that silently skips real solutions.

Summary

• Brute-force search tries candidates exhaustively, usually with little or no pruning.
• Backtracking builds candidates incrementally and abandons impossible branches early.
• Backtracking is most useful when partial constraints can eliminate large subtrees.
• Brute force is simpler and sometimes perfectly acceptable for small inputs.
• A recursive search is only true backtracking if it uses valid pruning logic.