# Leetcode 301 - Remove invalid parentheses

`Note:`

- We need to return all possible results, so
`DFS`

or`BFS`

is unavoidable. `BFS`

- Use two sets
`curSet`

(initialized as`s`

) and`nextSet`

. - For every str in
`curSet`

, check if there are valid ones before each iteration. If yes, it must be the result coz in BFS, the deeper the level is, the more operations we need to do. - If not, for each str in curSet, for each parenthesis in
`str`

, remove it and add it to`nextSet`

. - Finally,
`curSet = nextSet`

and we keep going.

- Use two sets

`Question:`

Given a string `s`

that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

`Example:`

1 | Input: s = "()())()" |

`Code:`

`BFS O(n*2^n):`

Time complexity is as know above coz there are `n`

possibilities to remove 1 char and the `max depth`

of tree is `2^n`

.

1 | /** |