Объясни генерацию перестановок
Вопрос
Объясни, как сгенерировать все перестановки массива без повторов, и какая у этого сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Описывает дерево решений: на уровне k выбираем k-й элемент
Использует массив used и путь path
Выбор, рекурсия, отмена
Сохраняет копию пути, а не ссылку
Сложность O(n · n!) времени, O(n) доп. памяти без учёта ответа
Что могут спросить следом
- Как быть, если в массиве есть дубликаты?
- Как сделать перестановки обменами на месте?
- Когда перебор вообще допустим по ограничениям?
Разбор
Представляю дерево решений: на первом уровне выбираю любой из n элементов, на втором любой из оставшихся и так далее. Держу path и массив used. В вызове: если длина path равна n, кладу в ответ копию path. Иначе перебираю все элементы, пропускаю использованные, для каждого делаю выбор (push и used = true), рекурсивно иду глубже и отменяю выбор (pop и used = false). Листьев n!, на копирование каждого O(n), итого O(n · n!). Доп. память O(n) на path, used и стек. При дубликатах сортирую и пропускаю элемент, если он равен предыдущему, а предыдущий на этом уровне не использован. Перебор уместен при n примерно до 8-10, дальше n! слишком велик.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.