Выбор ответа Middle Перебор с возвратом обновлено
Перестановки или сочетания
Вопрос
Чем рекурсия для перестановок отличается от рекурсии для сочетаний?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Сочетания идут вперёд с start, перестановки берут любой не used. В сочетаниях порядок не важен, поэтому следующий элемент берём только правее текущего (for (j = start; ...)).
Варианты ответа
- Ничем: обе перебирают все элементы на каждом уровне рекурсии
- Перестановки обходят дерево через стек, а сочетания через очередь (BFS)
- Сочетания идут вперёд с
start, перестановки берут любой неusedправильный ответ - Сочетания требуют предварительной сортировки, перестановки нет
Разбор
В сочетаниях порядок не важен, поэтому следующий элемент берём только правее текущего (for (j = start; ...)). В перестановках порядок важен, на каждом уровне пробуем любой ещё не использованный элемент.
- Отличие принципиальное.
- Обе обычно рекурсивны.
- Сортировка нужна только для пропуска дубликатов.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.