Задача №90 на LeetCode — это как собирать рюкзак в поход, но с хитростью: у вас есть одинаковые предметы, и вы не хотите брать с собой два одинаковых набора! Сегодня разберём, как генерировать все возможные комбинации без повторов. 🚀
Условие задачи (простыми словами)
🎯 Что такое "подмножество"?
Представьте, что у вас есть коробка с конфетами:
🍫 🍬 🍫 🍭
Подмножество — это любой набор конфет, который вы можете взять из коробки:
- Взять ничего: []
- Взять одну: [🍫], [🍬], [🍭]
- Взять две: [🍫,🍬], [🍫,🍫], [🍬,🍭]...
- Взять все: [🍫,🍬,🍫,🍭]
🔑 Главная хитрость этой задачи:
В коробке могут быть одинаковые конфеты (дубликаты), но наборы не должны повторяться!
Дано: [1, 2, 2]
✅ Правильные подмножества:
[], [1], [2], [1,2], [2,2], [1,2,2]
❌ Неправильно (дубликаты наборов):
[2] встречается дважды (из первого 2 или из второго 2) — но это ОДИН и тот же набор!
Ваша задача:
Дан массив чисел nums (может содержать дубликаты).
Верните все возможные подмножества без дубликатов наборов.
Порядок подмножеств и порядок чисел внутри — не важен.
🎮 Примеры "на пальцах"
Пример 1: nums = [1, 2, 2]
Шаг 1: Сортируем → [1, 2, 2] (важно для обработки дубликатов!)
Шаг 2: Генерируем подмножества:
Начинаем с пустого: []
Добавляем 1:
[] → [1]
Добавляем первый 2:
[] → [2]
[1] → [1,2]
Добавляем второй 2:
[] → [2] ❌ УЖЕ ЕСТЬ! Пропускаем
[1] → [1,2] ❌ УЖЕ ЕСТЬ! Пропускаем
[2] → [2,2] ✅ Новый!
[1,2] → [1,2,2] ✅ Новый!
Итог: [[], [1], [2], [1,2], [2,2], [1,2,2]]
Как решать?
Способ: "Дерево решений" (Бэктрекинг — интуитивный)
Идея: Представьте, что вы стоите перед каждой конфетой и решаете:
- 🅰️ Взять её в рюкзак
- 🅱️ Не брать её
Но есть правило: если конфеты одинаковые и стоят подряд — берём только первую, а остальные пропускаем, чтобы не было дубликатов!
Код решения (бэктрекинг):
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task90_subsetsII/Solution.java