Understanding the unconditional enumeration pattern

Many real-world problems may have multiple solutions, and to solve them, we may need to find and collect all the solutions. Backtracking is the ultimate brute-force technique to solve any problem that starts from an initial state, explores the entire problem space, and builds a solution incrementally. Unconditional enumeration is the most fundamental backtracking technique, which starts from an initial problem state, explores the entire problem space by making an independent set of choices from every state and collects the solution states and backtracks to make different choices.

It is important to note that any choice we make at a step is independent of any earlier choices; hence, we call this process unconditional enumeration.

The unconditional enumeration pattern is the classification of problems that can be solved using the unconditional enumeration backtracking technique.

The state space tree for unconditional enumeration is given below.

The state space tree for unconditional enumeration.

In this course, we will learn more about the unconditional-enumeration technique and how to identify a problem as an unconditional-enumeration pattern problem.

Unconditional enumeration

In unconditional enumeration, we begin with an initial problem state defined by some state variables. At every step, we can make one of many independent choices to reduce the size of the problem and move to another state. This process of making choices at every step is repeated recursively until we reach a solution state. As we make these choices and move from one state to another, we incrementally build the solution in some state variable.