Pruning: never build what cannot work

The difference between generating everything and filtering, and generating only the valid ones.

Generate and filter, and why not

The obvious approach to a constrained generation problem is to generate every candidate and keep the valid ones. It is correct and it does an enormous amount of pointless work.

For strings of length n over two symbols that is 2 to the n candidates regardless of how few are valid. When the valid ones are a small fraction, almost all of the search is wasted.

Why it works

Check the constraint at each choice instead

The alternative is to refuse a choice that already makes the candidate invalid. The branch is never taken, so the entire subtree beneath it is never explored.

That requires the constraint to be checkable on a partial candidate, which is the condition for this technique to apply. If validity can only be judged on a complete candidate, pruning is not available.

1def no_two_adjacent_ones(length):2    results, current = [], []3 4    def explore():5        if len(current) == length:6            results.append("".join(current))7            return8        for digit in "01":9            if digit == "1" and current and current[-1] == "1":10                continue               # would break the rule, never go there11            current.append(digit)12            explore()13            current.pop()14 15    explore()16    return results17 18print(no_two_adjacent_ones(3))19print(len(no_two_adjacent_ones(10)))

Quick check· 5 min

Which guards do you need?

You are generating balanced bracket strings with exactly n pairs, tracking opened and closed. Which pair of conditions allows exactly the valid strings and nothing else?

Place an opener when opened < n; place a closer when closed < openedPlace an opener when opened < n; place a closer when closed < nPlace either whenever the total placed is less than 2n, then validate at the endPlace an opener when opened <= closed; place a closer when closed < opened

Problem· 25 min

Generate Parentheses

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Generate and filter, and why not

The obvious approach to a constrained generation problem is to generate every candidate and keep the valid ones. It is correct and it does an enormous amount of pointless work.

For strings of length n over two symbols that is 2 to the n candidates regardless of how few are valid. When the valid ones are a small fraction, almost all of the search is wasted.

1def no_two_adjacent_ones(length):2 results, current = [], []3 4 def explore():5 if len(current) == length:6 results.append("".join(current))7 return8 for digit in "01":9 if digit == "1" and current and current[-1] == "1":10 continue # would break the rule, never go there11 current.append(digit)12 explore()13 current.pop()14 15 explore()16 return results17 18print(no_two_adjacent_ones(3))19print(len(no_two_adjacent_ones(10)))