# Backtracking - Generate Parentheses

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, Backtracking, Stack

## Problem

Given `n`

pairs of parentheses, write a function to *generate all combinations of well-formed parentheses*.

**Example 1:**

1
2

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

**Example 2:**

1
2

Input: n = 1
Output: ["()"]

## Solution

If you have ever solved these types of problem then you know use of `stack`

is very common to keep track of number of **Parentheses**. Before getting into the logic lets visualize the graph.

Here is the high level idea:

- Use DFS to find various paths.
- Keep adding
`(`

and call`dfs()`

until the number of open parentheses reaches`n`

- Keep adding
`)`

and call`dfs()`

only if number of close parentheses is less than the open parentheses.

Now let’s go through the **Example 1**, At first the Yellow box will run `3`

times (Yellow Box) and add `(((`

into the `stack`

. the backtracking (`pop()`

) won’t be executed here. Then on the 4th run, the yellow part won’t be executed as number of open will be equal to `N`

. Now the green box will run `3`

times and will produce `((()))`

.

Now the length of the generated sequence will have both `open==close==N`

. So we will add it to the `output`

and return.

At first the close (red) backtracking logic (`pop()`

) will be executed `3`

times. Then the open (blue) backtracking logic (`pop()`

) will be executed only once.

The close logic (green) will be executed again. This will add `)`

into the `stack`

. Similarly the rest of the program will continue running.

Visualizing the problem helps us to develop the intuition before trying to code it. Now let’s start by defining the variables.

We need an array to store the outputs, we also need a `stack`

. Luckily in python an array can also behave like a `stack`

.So lets define two variables.

1
2

output = []
stack = []

Define the `dfs()`

function. We need to keep track of open & close parentheses. So the `dfs`

will take both of them as argument.

1

def dfs(open_count, close_count):

Define the terminating condition. Whenever the `open_count`

and `close_count`

are equal to `n`

, we know we have a valid sequence.

1
2
3
4

def dfs(open_count, close_count):
if open_count == close_count == n:
output.append("".join(stack))
return

Now keep adding the open `(`

parentheses if the `open_count < n`

using `dfs()`

. Increment the `open_count`

by `1`

and once done backtrack by popping from the `stack`

.

1
2
3
4

if open_count < n:
stack.append("(")
dfs(open_count+1,close_count)
stack.pop()

Do the same for the `close_count`

, expect the logic is different. Add `close_count`

only if its `< open_count`

.

1
2
3
4

if close_count < open_count:
stack.append(")")
dfs(open_count,close_count+1)
stack.pop()

At the end, invoke the `dfs()`

and return `output`

.

1
2

dfs(0,0)
return output

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def generate_parentheses(n):
output = []
stack = []
def dfs(open_count, close_count):
if open_count == close_count == n:
output.append("".join(stack))
return
if open_count < n:
stack.append("(")
dfs(open_count+1, close_count)
stack.pop()
if close_count < open_count:
stack.append(")")
dfs(open_count, close_count+1)
stack.pop()
dfs(0, 0)
return output