Understanding the conditional enumeration pattern

Conditional enumeration is another fundamental backtracking technique that explores the entire problem space using backtracking and collects all the solutions. However, unlike unconditional enumeration (covered in the previous pattern lesson), in which choices at each step are independent of previous choices, in conditional enumeration, the set of choices at each step depends on the choices made in previous steps. To enumerate all solutions, we start from an initial state and, at each step, choose from a set of available choices to move to another state, eventually exploring the entire problem space.

It is essential to note that any choice we make at a step is dependent on the choices we made earlier, and hence we call this process conditional enumeration.

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

The state space tree for conditional enumeration.

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

Conditional enumeration

In conditional enumeration, we begin with an initial problem state defined by some state variables. At every step, we can make one of many dependent 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.

Consider the state space tree below, where we have an initial problem state and k dependent choices that we can make at each step. The depth of the problem space is denoted by n, which is the maximum number of choices we must make to reach a solution state. At every step, making a different choice may lead to completely different solution states in the end. We recursively make a series of choices until we reach a solution state, then backtrack to update our choices. In this way, we visit every solution state exactly once.