Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.

Для каждого элемента есть две возможности:
1. Включите текущий элемент в подмножество и повторите операцию для остальных элементов с оставшейся суммой.
2. Исключить текущий элемент из подмножества и повторить операцию для остальных элементов.
3. Наконец, если сумма становится равной 0, выведите элементы текущего подмножества.

Сложность: O(n^2)

Междугородние маршруты без интернета? Сделали!

В 2ГИС теперь можно строить маршруты между регионами офлайн.

Звучит просто, но за этим — куча инженерных решений... Например, чтобы всё это заработало, мы работаем с макрографом — он позволяет строить маршрут по крупным кускам, а потом достраивать начало и конец уже по детальному графу.

В статье — про архитектуру, организацию данных и предрасчёты. Для тех, кто любит алгоритмы и инженерные задачи 🕵️

\#2ГИС_алгоритмы

Головоломка, в которой требуется найти маршрут хода коня на шахматной доске, проходящий через все клетки только один раз.

Алгоритм:
1. Создаем шахматную доску n x n, где n - размерность доски.
2. Инициализируем текущую позицию коня на доске.
3. Помечаем текущую позицию как посещенную.
4. Проверяем, есть ли еще непосещенные клетки на доске:
- Если все клетки посещены, то задача решена, и мы можем вернуть найденный маршрут.
- Если не все клетки посещены, переходим к следующему шагу.
5. Находим все возможные ходы коня из текущей позиции:
- Проверяем, что следующий ход находится в пределах доски и не был посещен.
6. Для каждого возможного хода коня:
- Передвигаем коня на следующий ход.
- Рекурсивно вызываем алгоритм для новой позиции коня.
- Если рекурсивный вызов вернул true (маршрут найден), то возвращаем true.
- Если рекурсивный вызов вернул false, отменяем текущий ход и ищем другие возможные ходы.

Сложность: O(8^n), где n - размерность доски.

Чтобы найти количество диагоналей в n-стороннем выпуклом многоугольнике, можно воспользоваться следующей формулой:

Количество диагоналей = (n * (n - 3)) / 2

Эта формула выведена из того факта, что в выпуклом многоугольнике с n сторонами каждая вершина может быть соединена с любой другой вершиной диагональю, за исключением самой себя, соседних с ней вершин и двух соседних с ними вершин. В результате из каждой вершины можно провести n — 3 диагонали. Однако вы должны разделить это на 2, чтобы не считать каждую диагональ дважды (поскольку, например, соединение вершины A с вершиной B — это то же самое, что соединение вершины B с вершиной A).

Идея отдельной цепочки заключается в реализации массива в виде связанного списка, называемого цепочкой.

Здесь все элементы, которые хешируются в одном и том же индексе слота, вставляются в связанный список.

Преимущества:
⁃ Просто реализовать.
⁃ Хэш-таблица никогда не заполняется, мы всегда можем добавить в цепочку больше элементов.
⁃ Менее чувствителен к хэш-функции или факторам нагрузки.
⁃ Чаще всего используется, когда неизвестно, сколько и как часто ключей можно вставлять или удалять.

Недостатки:
⁃ Некоторые части хеш-таблицы никогда не используются
⁃ Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
⁃ Использует дополнительное пространство для ссылок