# Validate Parentheses

## Original Problem

1 | # Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. |

## Approach

As many of you have seem before, this is a classic problem that utilizes stacks.

Parenthese pairs has two requirements:

- left must go before right
- the type of the closing right must match the left

For an example, ‘(()}’ and ‘)()(‘ are not valid pairs

To satisfy the first requirement we can use indexing (dictionary to string) to ensure the closing one is the same type as opening one, and to perserve the second characteristic we can use a stack.

## Implmentation

1 | def valid_parentheses(s_parens): |

Notice in the end we only return True when the stack is empty, this way if there is any unclosed paren in the stack it is still invalid.

https://leetcode.com/problems/valid-parentheses/

# Generate Valid Parentheses

## Original Problem

1 | # Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. |

## Approach

Different then the problem above, this question is asking us to generate all possible valid combinations of parens given the number of pairs.

A common reaction is to use nested for loops, but it will be very difficultf since there are many variations not just ‘()()()’ or ‘((()))’.

To solve this problem we can use a technique call backtracking, it’s essentially a variation to recursion.

## Implmentation

1 | def generate_parenthesis(n): |

Notice the condition to stop the recursions are left < n and right < left, it restrict to be less then n, and also restricted the produciton of an right before a left

It’s helpful to **draw out** the recursion call stack, it’ll be much clear to you why the conditions are set up this way.

https://leetcode.com/problems/generate-parentheses/description/