Search Space

Search space is the set of possible candidates, choices, states, or paths an algorithm may examine.

Understanding the search space is often the first step toward understanding why a direct solution is too slow.

Core Idea

An algorithm can be seen as moving through possibilities. Brute force explores many of them directly. Backtracking cuts off impossible branches. Dynamic programming avoids solving the same state repeatedly.

The size of the search space often determines the difficulty of the problem.

Python Example

def all_binary_strings(length):
    result = []
 
    def build(prefix):
        if len(prefix) == length:
            result.append(prefix)
            return
 
        build(prefix + "0")
        build(prefix + "1")
 
    build("")
    return result

For length n, there are 2 ** n binary strings in the search space.

Common Confusions

Search space is not the same as input size. A small input can produce a huge number of possible choices.

The algorithm may not visit the entire search space. The point is to understand what could be explored and how the algorithm controls that exploration.

When To Use It

Use search-space reasoning for combinations, permutations, paths, game states, recursive choices, and optimization problems where the simple solution tries many candidates.