Data Structures and Algorithms

In my last post I made an argument that felt, to me, like stating the obvious — but one I couldn’t find anyone else putting into words: backtracking is just counting. If your search space is a product of small independent choices, a depth‑first walk through it is the same object as incrementing a mixed‑radix number — an odometer. And a “prune” is just you refusing to descend into a number you can already see is doomed. I wrote the full version of that up: backtracking as a bijection to the integers. ...

The Combinatorial Gap When we approach a backtracking problem, we are essentially dealing with two different magnitudes of space. First, there is the Total Theoretical State Space. If we have $N$ decision variables, each with a cardinality (base) of $B_i$, the total number of possible configurations is the product: $\prod_{i=1}^{N} B_i$. This represents an astronomical number of potential states. Second, there is the Effective Search Space—the set of paths that remain viable under specific constraints. ...