Reverse-Search Algorithm

Reverse-search algorithms are a class of algorithms for generating every object of a given size from certain classes of combinatorial objects, such as the vertices of a convex polytope or the cells of a hyperplane arrangement. David Avis and Komei Fukuda introduced the technique in 1991 for polytope and arrangement problems and formalized it as a general method in 1996. A reverse-search algorithm organizes the objects being enumerated into a spanning tree and explores that tree with a depth-first search, which lets it generate results using very little memory and in polynomial time per object, without producing any duplicates. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/