Where it runs
1. The problem
Subsets, permutations and combinations were all listed by trying everything: each branch was tried, and the ones that reached the end were kept. The prune in the last lesson only looked at a count: are enough items left? Now the prune follows a rule. A branch is dropped the moment it breaks a constraint, long before the end. Then no time goes into finishing an arrangement that would turn out wrong anyway.
You need every valid way to place n pairs of brackets. For n = 2 that is (()) and ()(). The string )( is not valid: it closes a bracket that was never opened. (() is not valid either: it opens more brackets than it closes.
You could build every string of length 2n made of ( and ) and keep the valid ones. But for n = 6 that is 4,096 strings, and only 132 of them are valid. Better to never build the invalid ones at all.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that generate only valid strings or splits, where a rule can be checked halfway. Check the rule before each step and cut the branch the moment it breaks.
The lesson task exactly, with open below n and close below open.
Never add a letter equal to the last one, generate in a, b, c order, and stop at the kth string.
Cut a part of 1 to 3 digits and drop the branch at once if it is above 255 or has a leading zero.
Cut only where the prefix is a palindrome, checked with two pointers, then recurse on the rest.