Insight Vault

Search Space

3 min read

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.

The search space is not always stored explicitly. It may be implicit in recursive calls, graph transitions, possible subsets, possible paths, or possible parameter values.

Function Contract

all_binary_strings(length) expects a non-negative integer length.

It returns a list of every binary string of that length. The output has 2 ** length strings, so the function is only reasonable for small lengths.

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.

Drawing the Space

For length = 3, the choices form a tree:

""
"0", "1"
"00", "01", "10", "11"
"000", "001", "010", "011", "100", "101", "110", "111"

There are three choice levels and two choices at each level, so there are 2^3 complete strings.

Complexity of the Example

all_binary_strings(length) produces 2^length strings. Any algorithm that explicitly returns all of them needs at least O(2^length) time just to write the output.

The recursion depth is O(length), but the result list stores all generated strings, so the output space is also exponential.

Controlling the Space

Algorithms improve brute force by controlling the search space:

  • Pruning removes branches that cannot lead to an answer.
  • Memoization avoids revisiting the same state.
  • Greedy choice avoids exploring alternatives when one choice can be proven safe.
  • Binary search removes half the candidates at each step.

The technique depends on what structure the search space has.

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.

Another common mistake is describing only the final answers. The search space also includes partial choices and intermediate states if the algorithm visits them.

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.

When stuck, ask: what are the possible states, how many are there, and which transitions move from one state to another?

The Main Point

Search space is the set of possibilities an algorithm may consider. Naming states, choices, and count of possibilities often explains why a direct solution is too slow.

Backlinks

Graph

Depth 1