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.