Backtracking
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.
Tip
How much that saved
For length 10 there are 1024 candidates and 144 valid ones. The pruned search visits only the nodes leading to those 144, so roughly seven eighths of the work never happens, and the ratio gets worse with length.
Those counts are Fibonacci numbers, which is a nice hint that a counting version of this problem is a dynamic programming exercise rather than a search. When only the count is wanted rather than the items, generation is almost always the wrong tool.
Key idea
Pruning with counters instead of inspection
Checking the last character works for a local rule. Many constraints are about totals, and those are better tracked as counters carried down the recursion.
Consider building a balanced bracket string. Two counters, how many openers used and how many closers used, are enough to express both rules: never use more openers than allowed, and never use more closers than openers.
Those two conditions are exactly the branch guards. There is no validity check at the end at all, because nothing invalid is ever built.
Why it works
Derive the guards, do not recall them
For any constrained generation, write the rules as statements about counts, then convert each into a condition on whether a choice is allowed.
A closer is allowed only when it would not exceed the openers placed so far. An opener is allowed only when the total limit has not been reached. Read those two sentences and the code is direct.
That derivation is the entire problem below. Do it on paper before writing anything, and the implementation is five lines.
Edge cases
The base case is a count, not a check
When nothing invalid is ever built, reaching the target length means the candidate is valid by construction. So the base case records unconditionally rather than testing anything.
A solution that still validates at the base case is a sign the pruning is incomplete, and it is worth looking for the branch that is not being guarded.
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?
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.