search space
The set of all candidate solutions an algorithm might consider, often pictured as a tree of choices.
In more detail
Backtracking walks the search space depth-first and pruning shrinks it. Its size, such as n factorial orderings or 2^n subsets, tells you how hopeless an exhaustive search would be.
Related terms
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- decision tree — A tree in which each internal node is a question or choice and each path from the root to a leaf is one complete outcome.
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.
Taught in
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers