LeetCode 40. Combination Sum II | Метод «брать или не брать» | Пропуск дубликатов | Решение за се...
Решение задачи «Сумма комбинаций II» на LeetCode 40 на Java с использованием метода обратного отслеживания. В этом видео рассматривается вся задача «Сумма комбинаций II»: каждое число используется только один раз, повторяющиеся комбинации пропускаются, а также используется шаблон пропуска повторяющихся комбинаций, который исправляет ошибку превышения лимита времени (TLE). «Сумма комбинаций II» — более сложная версия задачи «Сумма комбинаций I». На LeetCode 40 каждое число может быть использовано только один раз, и ответ не должен содержать повторяющихся комбинаций. При попытке использовать наивное решение с обратным отслеживанием вы получите неверные ответы с повторяющимися комбинациями, такими как [1,2,5] и [2,1,5], появляющимися вместе. В этом видео это исправлено с помощью одного простого правила: отсортировать кандидатов, а затем пропустить число всякий раз, когда предыдущее равное число было отклонено. Этот единственный шаблон пропуска повторяющихся комбинаций превращает неудачный перебор в правильное решение за считанные секунды. Начинаем с дерева рекурсии для кандидатов [1, 1, 2] с целевым значением 2 и перебираем каждую подпоследовательность: решение о принятии или непринятии на каждом индексе, сумма равна целевому базовому случаю и возврат, который удаляет последний элемент после каждого рекурсивного вызова. Запускаем первую версию и наблюдаем, как она выдает ошибку при повторяющихся комбинациях, затем применяем исправление сортировки с пропуском в Java: i больше startIndex И candidates[i] равно candidates[i-1]. Вторая попытка завершается ошибкой «Превышен лимит времени», поэтому добавляем отсечение — если текущая сумма превышает целевое значение, немедленно возвращаемся. Финальный код проходит успешно, и мы пошагово разбираем полную реализацию на Java. ⏱️ Разделы: 00:00 Сумма комбинаций II – Почему интервьюеры так часто задают этот вопрос 01:00 Условие задачи LeetCode 40 02:00 Правило: Каждое число используется только один раз в комбинации 02:30 Повторение подпоследовательностей – брать или не брать 05:00 Количество подпоследовательностей = 2^n 05:30 Дерево рекурсии с индексом и накопительной суммой 09:00 Базовый случай: idx == n и sum == target 10:00 Параметры рекурсивной функции 11:00 Код на Java: Генерация комбинаций (брать/не брать) 15:00 Код базового случая: Проверка равенства суммы целевому значению 16:00 Проблема: Дублирующиеся комбинации 17:30 Решение: Сортировка и пропуск дубликатов (вместо множества) 19:00 Почему сортировка приводит к появлению дубликатов Соседи 20:30 Пропуск повторяющегося блока с помощью цикла While 22:00 Отсечение: остановка, когда сумма превышает целевое значение Полный код: https://github.com/Shaanworkspace/YOUTUBE-DRIVE Больше от Shaan Labs: Ежедневные решения LeetCode → https://github.com/Shaanworkspace/YOUTUBE-DRIVE/tree/main/Leetcode_Daily Часто задаваемые вопросы: Что такое «Сумма комбинаций II» в LeetCode 40? В LeetCode 40 вам нужно найти все уникальные комбинации в массиве кандидатов, сумма чисел которых равна целевому значению. Каждое число может быть использовано только один раз, и набор решений не должен содержать повторяющихся комбинаций. Для кандидатов [1, 1, 2] и целевого значения 2 ответ — [1, 1] и [2]. В чем разница между «Суммой комбинаций I» и «Суммой комбинаций II»? В Combination Sum I одно и то же число может быть использовано любое количество раз. В Combination Sum II каждое число может быть использовано только один раз, и входные данные могут содержать дубликаты. Эти два изменения приводят к необходимости сортировки и пропуска дубликатов в LeetCode 40. Зачем сортировать массив в Combination Sum II? Сортировка сближает все равные значения, поэтому после отклонения числа можно пропустить каждое последующее равное число в одном цикле while. Без сортировки равные числа разбросаны, и пропуск не работает. Зачем пропускать дубликаты в Combination Sum II? Если не пропускать дубликаты, одна и та же комбинация генерируется несколько раз, поскольку равные числа на разных индексах дают идентичные результаты. Условие пропуска i больше startIndex И candidates[i] равно candidates[i-1] отклоняет блок равных чисел после первого, сохраняя уникальность ответа. Какова временная сложность решения Combination Sum II с возвратом? В худшем случае временная сложность составляет O(2 в степени n), потому что каждый элемент может быть взят или пропущен. Пространственная сложность составляет O(n) для стека рекурсии плюс O(n) для текущего списка комбинаций. Сумма, превышающая целевой показатель отсечения, значительно сокращает практическое время выполнения. Как удалить дубликаты в алгоритме обратного отслеживания для LeetCode 40? Сначала отсортируйте кандидатов. Затем в рекурсивном цикле пропускайте индекс, если он больше начального индекса, а текущее число равно предыдущему. Эта единственная проверка удаляет все повторяющиеся комбинации без использования HashSet. #LeetCode #Backtracking #Java #CombinationSum #DSA
Название:
LeetCode 40. Combination Sum II | Метод «брать или не брать» | Пропуск дубликатов | Решение за се...
Категория:
Разное