State Space Exploration Superset Professional Playbook

Use this guide when a problem can be solved by recursive calls, graph/grid movement, choices, memoization, BFS, tree traversal, string positions, or range splitting, and you need to decide what the call really means.

Read in this order:

1. Learn the superset family map.
2. Learn the five universal questions.
3. Learn the state-versus-unit vocabulary bridge.
4. Learn the forward-work versus upward-work distinction.
5. Translate the problem with the unified workflow.
6. Pick the execution family.
7. Use the merged translation table for pattern recognition.
8. Study the canonical examples.
9. Study the dry runs.
10. Use the decision rules, failure modes, performance notes, and cheat sheets.

This guide intentionally repeats the same questions from several angles. That is useful because most mistakes come from choosing the engine too early.

Do not start with:

This is recursion.
This is DP.
This is graph.
This is string.

Start with:

What does one call/state/unit know?
What can it legally do next?
What must it return?

A problem is a world. A state is one place in that world. A move takes you to another place. A stop condition says when a path is done. An answer type says what comes back.

I am here.
I know these facts.
These moves are legal.
This move changes the state.
When I stop, I return or record this kind of answer.

Visual:

The beginner question is always:

    What is the world?
    Where am I standing?
    Where can I move next?
    What do I remember?
    What happens when I stop?

1) Matrix / grid world

problem: explore land cells, find a path, count a region, search a word

        c0   c1   c2   c3
      +----+----+----+----+
r0    | .  | #  | .  | .  |
      +----+----+----+----+
r1    | .  | S  | .  | .  |
      +----+----+----+----+
r2    | .  | .  | #  | .  |
      +----+----+----+----+

state = current cell = (r1, c1)

possible next states:

                (r0,c1) blocked
                       ^
                       |
        (r1,c0) <--- (r1,c1) ---> (r1,c2)
                       |
                       v
                    (r2,c1)

memory can be:
visited cells, current path, distance layer, remaining keys, current word index

classification:
mark and move only          -> pure explorer / flood fill
need shortest path          -> BFS explorer
need choose letters in path -> backtracking explorer
same cell plus extra facts  -> richer state, such as (r,c,keys) or (r,c,wordIndex)

2) Tree world

problem: traverse, compute depth, find diameter, collect paths

                   A
                /  |  \
               B   C   D
             /   \
            E     F

state = current node = B

possible next states:

              parent A
                 ^
                 |
                 B
               /   \
              E     F

If the tree is rooted and you only move downward:

    B -> E
    B -> F

If the problem treats the tree like an undirected graph:

    B -> A
    B -> E
    B -> F

classification:
visit nodes and mark/collect       -> traversal explorer
return height/count/best upward    -> tree summary recursion
split left/right and rebuild value -> divide/recombine style

3) String index world

problem: decode, segment, match, partition, scan

string:

    s = "leetcode"
         0 1 2 3 4 5 6 7 8
         l e e t c o d e
         ^
       state i=0

possible next states in Word Break:

    i=0
     |
     | take "leet"
     v
    i=4
     |
     | take "code"
     v
    i=8 stop

state = index i
move = choose a valid word/piece starting at i
stop = i == len(s)
memory = memo[i] if the same index repeats

classification:
single pass with reusable border/hash -> string structure
choose substrings and undo            -> backtracking
same index repeats                    -> DP explorer

4) Choice / path world

problem: subsets, permutations, partitions, N-Queens

nums = [2, 7, 9]

state = (index, current_path)

                         (i=0, path=[])
                         /             \
                    skip 2             take 2
                       /                 \
              (i=1, [])              (i=1, [2])
              /       \              /          \
         skip 7      take 7     skip 7        take 7
           |            |          |              |
       (i=2, [])    (i=2,[7])  (i=2,[2])   (i=2,[2,7])

move = choose one legal branch
undo = remove the choice before trying the next branch
stop = index == len(nums)
answer = record the current path, or count valid paths

classification:
concrete path/output matters -> choice explorer / backtracking
only best count/value matters -> often DP after compressing the state

5) Two-index DP world

problem: LCS, edit distance, interleaving string, distinct subsequences

state = one cell in an index grid = (i, j)

        text2 index j
           0     1     2
        +-----+-----+-----+
 i=0    |0,0  |0,1  |0,2  |
        +-----+-----+-----+
 i=1    |1,0  |1,1  |1,2  |
        +-----+-----+-----+
 i=2    |2,0  |2,1  |2,2  |
        +-----+-----+-----+
             ^
             |
        current state could be (2,1)

possible next states depend on the recurrence:

    LCS:
        if chars match:    (i,j) -> (i+1,j+1)
        if chars differ:   (i,j) -> (i+1,j) and (i,j+1)

    Edit distance:
        insert:            (i,j) -> (i,j+1)
        delete:            (i,j) -> (i+1,j)
        replace/match:     (i,j) -> (i+1,j+1)

memory = dp[i][j]
stop = one index reaches the end
answer = value returned for this pair of suffixes/prefixes

classification:
same (i,j) repeats and returns a value -> DP explorer
moving through characters is the world -> string state explorer

The shared picture:

    problem world -> current state -> legal next states -> stop/return

What changes between families is what "return" means:

pure explorer:      mark and move
choice explorer:    record a completed path
DP explorer:        return cached answer for this state
BFS explorer:       return shortest layer distance
string explorer:    move through index/pair/path/match state
recombine:          return child summary to parent

For divide/recombine, the wording changes:

I own this unit.
This is the smallest direct answer.
I split into these child units.
Each child returns this summary.
I combine summaries into my own summary.

Same recursion. Different emphasis.

The state-space wording and divide/recombine wording are two views of the same recursive skeleton.

Visual:

State exploration:

state A --move--> state B --move--> state C
   |                 |                 |
 mark/record/cache  mark/cache        stop

Divide/recombine:

               parent summary
              /              \
     left child summary    right child summary
          /                      \
      base unit                base unit

Translate in this order.

What must I return?

index
path
row, col
node
node plus bounds
amount
capacity
i, j
left, right
mask
trie_node
automaton_state
range [lo, hi]
token interval
segment-tree interval

contains every fact that changes future choices or answers

does not include facts already derivable from the state

(index, remaining, path)

(index, remaining)

grid:
    up, down, left, right

lock:
    rotate one wheel up or down

string index:
    consume one character, two digits, or one dictionary word

two-string DP:
    match both, skip first, skip second, edit

tree:
    visit left child, visit right child

divide/recombine:
    split range, split traversal arrays, split at operator

index == n
remaining == 0
node is None
out of bounds
visited already
target reached
range is empty
range has one item
token is a number

Need all valid paths or constructions?
    -> backtracking

Need to mark reachable nodes/cells?
    -> pure DFS/BFS traversal

Need shortest equal-cost path?
    -> BFS

Can the same state repeat?
    -> DP

Does a small set belong in the state?
    -> bitmask

Does parent need child summaries?
    -> tree summary or divide/recombine

Does string progress or mismatch memory dominate?
    -> string state / string structure

Choice explorers build concrete objects.

Use when:

• the output asks for all combinations, permutations, partitions, boards, or paths
• a partial answer is being built
• choices must be tried one by one
• sibling branches must not share mutations

Core idea:

choose
recurse
undo

Examples:

Subsets
Permutations
Combination Sum
Generate Parentheses
Restore IP Addresses
Palindrome Partitioning
Word Search

Backtracking skeleton:

path = []

search(state):
    if complete:
        answers.add(copy(path))
        return

    for choice in legal_choices(state):
        apply choice
        search(next_state)
        undo choice

The important rule:

Only copy the path when recording an answer.

A bitmask stores a small set inside an integer.

Use when:

• the number of items is small
• each item has a stable index
• you need cheap copy, membership, hashing, or visited keys

Examples:

used indexes in permutations
visited nodes in shortest path visiting all nodes
collected keys in a grid
selected skills in smallest sufficient team
available digits in Sudoku

Operations:

bit = 1 << i

contains i:
    mask & bit

add i:
    mask | bit

remove i:
    mask & ~bit

all n items:
    mask == (1 << n) - 1

Visual:

items: A B C D
index: 0 1 2 3
mask:  1 0 1 0

set = {A, C}

Bitmask is not an algorithm family by itself. It is a representation used by backtracking, DP, and BFS.

BFS explorers ask:

What is the shortest equal-cost path to a target state?

Use when:

• every move has the same cost
• target can be recognized
• shortest number of moves is required
• state space is bounded or can be pruned

Examples:

Open the Lock
Word Ladder
Minimum Genetic Mutation
Sliding Puzzle
Rotting Oranges
Shortest Path Visiting All Nodes
Shortest Path in Grid With Obstacles Elimination

Visited timing:

mark visited when pushing into the queue

Why:

the first time a state is pushed, it has already been reached by the shortest layer

If edge costs differ, use weighted shortest-path logic instead of plain BFS.

Tree problems often sit between pure traversal and recombine.

Simple traversal:

preorder(node):
    visit node
    preorder(left)
    preorder(right)

Simple returned summary:

height(node):
    return 1 + max(height(left), height(right))

Bridge summary:

diameter(node):
    left_height = height(left)
    right_height = height(right)
    best = max(best, left_height + right_height)
    return 1 + max(left_height, right_height)

True divide/recombine:

build_tree(pre_range, in_range):
    root = preorder first
    split inorder around root
    root.left = build(left ranges)
    root.right = build(right ranges)
    return root

Boundary:

Traversal:
    moving through existing structure

Tree summary:
    moving through existing structure and returning small facts

Tree construction:
    rebuilding a new structure from split evidence

Start with correctness. Then optimize in this order:

1. Choose the right execution family.
2. Make the state complete.
3. Make the state minimal.
4. Prune illegal branches early.
5. Memoize repeated states.
6. Use bitmasks for small sets.
7. Encode BFS states compactly.
8. Use arrays for dense DP.
9. Use child summaries to avoid recomputing cross work.

state_id = ((mask * rows) + row) * cols + col