---
round: 1
ticket_no: 9
source_no: 23
slug: remove-invalid-parentheses
topic: DFS / BFS
difficulty: Hard
leetcode_id: 301
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 09 — Remove Invalid Parentheses

## Условие (как предъявлено)

Дана строка `s`, состоящая из букв и скобок `(` и `)`. Нужно удалить минимальное число неверных скобок, чтобы строка стала валидной, и вернуть все уникальные варианты получившихся строк.

```
Input:  s = "()())()"    →  ["(())()","()()()"]
Input:  s = "(a)())()"   →  ["(a())()","(a)()()"]
Input:  s = ")("         →  [""]
```

Constraints: `1 <= length <= 25`, максимум 20 скобок.

## Ответ

> Значит, идея такая, что мы наполняем сначала. Ну, во-первых, у нас должен быть метод проверки: текущая строка корректна или нет. Значит, она работает по схеме. У нас есть счётчик открывающихся скобок и счётчик закрывающихся. Если он вдруг включается, мы проходим. Вот если вдруг отрицательные становятся, то есть каждое открытие — это плюс, каждое закрытие — это минус. Если вдруг у нас отрицательное число, значит некорректная строка. То есть у нас должен быть метод такой проверки последовательности: оно корректно или нет. Дальше мы делаем очередь, удаляем. То есть, у нас есть, например, строка, она некорректна. Значит, нам нужно идти дальше, значит, её попытаться модифицировать. Мы добавляем в очереди все её подстройки, то есть не подстройки, точнее, её вариации, когда мы удаляем одну из этих, один из одной из скобочек удаляем случайно как бы по очереди: сначала без первой скобочки добавили в очередь, без второй скобочки, и так далее. То есть проходим по очереди, добавляем такие вариации данной строки в очередь, дальше. Когда мы её заполнили, мы берём оттуда. Ну как бы, не то чтобы все элементы, а берём начальный конечный индекс. То есть понимаем, сколько на данный момент там находится, и начинаем через них итерироваться. То есть у нас одноранговый сейчас проходим. Проверяем их, вот, походу, и если, например, первый элемент смотрим, он валидный или нет. Если валидный, то мы состояние нашего модифицируем, что мы уже нашли результат на этом уровне. То есть на следующий уровень мы переходить уже не будем. Дальше просто доходим по текущей секции данной очереди до конца, если вдруг ещё какие-то решения найдутся, мы их тоже добавляем. Здесь важный элемент по поводу нужно составить ещё такой тоже хэш уникальных значений или массив уникальных значений тех, которые мы уже проверяли, чтобы мы не проверяли повторно. То есть, если мы какой-то уже проходили, мы его должны в отдельную структуру добавить. Ну, предположим, массив с проверкой уникальности, либо хэш, где элемент, или сет, например, можно использовать специально это. Так что тут ещё можно сказать? Здесь есть ещё улучшение этого механизма, чтобы удалять не абстрактно, чуть более тонко, вот, но этот алгоритм сложнее, то есть надо пройтись тоже по счётчику посмотреть, где у нас отрицательное значение происходит. Вот, и начит, но здесь я не знаю. Короче, вот чуть более тонко можно это пройти по-другому.

## Разбор

**Что верно:** BFS по уровням (уровень = число удалённых скобок), проверка валидности счётчиком баланса, visited против дублей, остановка на первом уровне с решениями; плюс упомянут более быстрый DFS со счётчиками лишних скобок — это эталонный подход.

**Что упущено и ошибки:** не названа сложность O(n·2^n) по времени и O(2^n) по памяти; не проговорено определение валидности: баланс нигде не отрицателен и в конце равен нулю.

**Эталонная идея:** BFS по уровням с visited и ранним стопом; либо DFS с rm_open/rm_close и отсечениями (память O(n)).

**Сложность:** BFS: время O(n·2^n), память O(2^n); DFS: время O(2^n), память O(n)

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/02-extra/02-dfs-bfs/23-remove-invalid-parentheses.md`](../../algo-solutions/02-extra/02-dfs-bfs/23-remove-invalid-parentheses.md)