---
# System prepended metadata

title: '[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)'
tags: [Leetcode, Stack, Medium]

---

# [Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)
###### tags: `Leetcode`, `Medium`, `Stack`

## Approach
* We will use recursive approach to solve this problem
* If there are `n` opening brackets then there will be `n` closing brackets
* For every open bracket added to the stack, we will increment the `open` counter and recursively call the function. Then pop the bracket from the stack
* For every close bracket added to the stack, we will increment the `close` counter and recursively call the function. Then pop the bracket from the stack
* If `open` == `close` then we will add that combination of brackets to the result list
* return 

## Code
``` python
from typing import List


class GenerateParentheses:
    def generate_parentheses(self, n: int) -> List[str]:
        stack, result = [], []

        def backtrack(opened: int, closed: int):
            if opened == closed == n:
                result.append("".join(stack))
                return
            if opened < n:
                stack.append('(')
                backtrack(opened + 1, closed)
                stack.pop()
            if closed < opened:
                stack.append(')')
                backtrack(opened, closed + 1)
                stack.pop()

        backtrack(0, 0)
        return result


print(GenerateParentheses().generate_parentheses(7))
```