Pattern visualizer
Generate Parentheses
Instead of generating every possible string of length 2n and filtering out the invalid ones, build only valid strings from the start: track how many '(' and ')' have been placed, allow a '(' whenever fewer than n have been used, and allow a ')' only when fewer close-brackets than open-brackets have been placed so far (otherwise it would go negative-balance, i.e. invalid). Every complete path this reaches is automatically well-formed. Animated on: n = 3 — generate all combinations of 3 well-formed pairs of parentheses..
Add '(' whenever possible, ')' only when it stays valid
n=3: build every valid combination of 3 pairs by backtracking. A '(' can be added anytime we haven't used all 3 yet; a ')' can only be added if it wouldn't outnumber the '(' placed so far (else the string becomes invalid).
1FUNCTION backtrack(path, open, close):2 IF open equals n and close equals n:3 add path to results; RETURN4 IF open < n:5 backtrack(path + '(', open+1, close) (add an open bracket)6 IF close < open:7 backtrack(path + ')', open, close+1) (add a close bracket only while it stays valid)
← / → step · space play · Home restart