Как переставить символы в строке — Генерация всех перестановок строки

Бесплатный 5-дневный мини-курс: https://backtobackswe.com Попробуйте нашу полную платформу: https://backtobackswe.com/pricing 📹 Интуитивно понятные видеообъяснения 🏃 Запускайте код во время обучения 💾 Сохраняйте прогресс ❓ Новые, ранее не встречавшиеся задачи 🔎 Получите все решения Задача: Дана строка. Распечатайте все перестановки этой строки и верните массив с ними. Дубликаты не допускаются. В подобных задачах тот факт, что это строка, и тот факт, что это массив, взаимозаменяемы. Перестановку элементов в массиве мы будем производить так же, как и в строке. Почему это задача с возвратом? Потому что мы размещаем элемент, а затем исследуем все возможные варианты. Всякий раз, когда перед нами стоит задача типа «сгенерировать» или «вычислить», и она представляет собой выражение нескольких точек принятия решений, составляющих более широкий набор возможностей… у нас есть метод обратного отслеживания (Backtracking). Три ключа к методу обратного отслеживания: Наш выбор Какой символ мы помещаем в «слот» Наши ограничения На самом деле никаких… но в каждой точке принятия решения у нас будет меньше символов для работы из-за наших предыдущих решений. Наша цель Пусть n — длина строки. Поместите n символов. Сложность Время: O(n * n!) — Существует n! перестановок, и добавление каждой из них в результирующий массив занимает O(n) времени. Пространство: O(n) — Мы не возвращаем массив, поэтому пространство линейное, поскольку наша рекурсия будет вложена максимум в n элементов, так как мы делаем n вариантов размещения. — Если бы мы хранили и возвращали массив, наша пространственная сложность была бы O(n * n!), так как у нас было бы n! перестановок, и каждая перестановка будет иметь длину n. Если мы будем считать возвращаемый массив всех строк перестановок НЕ частью пространства, то стек вызовов будет доминировать в пространстве. Мы снова возвращаемся к O(n). ++++++++++++++++++++++++++++++++++++++++++++++++++ HackerRank:    / @hackerrankofficial   Тушар Рой:    / tusharroy2525   GeeksForGeeks:    / @geeksforgeeksvideos   Джарвис Джонсон:    / vsympathyv   Success In Tech:    / @successintech   ++++++++++++++++++++++++++++++++++++++++++++++++++++ Этот вопрос — номер 16.3 в замечательной книге «Элементы программирования». «Интервью» Аднана Азиза