> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph-dfs-bfs/remove-invalid-parentheses.md).

# Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

**Note:** The input string may contain letters other than the parentheses `(` and `)`.

> Example 1:\
> Input : "( ) ( ) ) ( )"\
> Output : \["( ) ( ) ( )", "( ( ) ) ( )"]
>
> Example 2 :\
> Input : "(a)( ) ) ( )"\
> Output : \["(a)( ) ( )", "(a( ) ) ( )"]
>
> Example 3:\
> Input: ") ("\
> Output: \[" "]

**자료구조** : Queue, Set이용

**알고리즘**\
input String의 0번째 index 부터 마지막 index까지 하나씩 제거해서 유효성 검사한다.\
1\. input String을 큐에 넣는다.\
2\. 큐에서 string을 빼면서 유효성 검사한다.\
   큐에서 뺀 string인 str이 valid하다면 result가 된다.  그리고 더이상 반복문을 수행하지 않아도 된다.\
   큐에서 n개를 제거한 string인 str이 invalid하다면, 그 다음 n개를 제거한 string을 수행한다.**(BFS)**\