Subset DP is dynamic programming indexed by subsets of a finite ground set, usually encoded by bit masks. A recurrence builds a subset from smaller subsets or removes one chosen element. There are subsets of an -element set, so many such methods require exponential space or time despite avoiding factorial enumeration.
For a shortest path visiting a given set, stores the best cost of a path visiting exactly and ending at . The recurrence retains the endpoint because it controls the next edge cost. Initial states and prohibited edges must be specified separately.
New to topics? Read the docs here!