Expert · Backtracking · 234 of 264
All bracket patterns
Print every balanced arrangement of n pairs of round brackets, in dictionary order (where ( comes before )).
Input: n (1 to 6). Output: one arrangement per line.
Examples
Input
3
Output
((())) (()()) (())() ()(()) ()()()
Input
1
Output
()
One more test checks other inputs when you press Check.
Stuck? The idea behind backtracking
Build an answer one choice at a time; when a choice leads nowhere, undo it and try the next. Recursion keeps track of where you are.
Check as early as you can whether a partial answer can still work, so dead ends are left quickly.
def subsets(items, chosen=[]):
if not items:
print(chosen)
return
subsets(items[1:], chosen + [items[0]])
subsets(items[1:], chosen)
subsets([1, 2])Watch for: Changing a shared list without undoing the change afterwards leaves the next choice with the wrong start.