Разбор задачи 90. Subsets II c Литкода
https://leetcode.com/problems/subsets-ii/description/
Условие
Дан массив чисел nums который может содержать дубликаты, верни все возможные подмножества (the power set).
Результат не должен содержать повторяющихся подмножеств. Верните результат в любом порядке.
Ввод: nums = [1,2,2] Вывод: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Ввод: nums = [0] Вывод: [[],[0]]
Решение
Мы видим из примера, что здесь не учитывается порядок, а учитваются сами элементы, если мы добавили [1,2], то мы не добавляем [2,1].
Возьмем массив [1, 2, 1].
Если мы добавим в результат первый и третий элемент ([1, 2]), а потом добавим второй и третий элемент ([2, 1]), то последний случай будет считаться как дубликат.
Чтобы узнать, является ли [2,1] дубликатом для [1,2], мы можем отсортировать, числа в этих массивах по возрастанию: [1,2] [1,2], и тогда нам будет легче сравнивать два массива.
Если мы отсортируем весь входной массив изначально, то у нас все подмножества сразу будут содержать числа по возрастанию.
Поэтому первым делом отсортируем исходный массив.Array.Sort(nums);
Итак, мы формируем очередное подмножество ([], [1], [1, 2], и т.д.)
Проверяем, а было ли добавлено такое же ранее, если да, то не добавляем.
Если нет, то добавляем.
Как нам проверить, что подмножество было добавлено ранее?
Один из вариантов пробегать по текущему результату в поиске дубликата. Это сложность O(n).
Другой вариант - воспользоваться хэш-сетом.
Заведем переменную типа HashSet<string>. Назовем её added ("добавлено").
Текущее подмножество мы переводим в строку, соединяя числа через делиметр, (например, через запятую), чтобы избежать такого случая, когда у нас есть, например, массив [-1, 0, -10], и выборки [-1, 0] и [-10] преобразуются в одну и ту же строку "-10". Далее мы ищем эту строку в хэш-сете, если строка там есть, значит текущее подмножество не добавляем в результат. Если строки нет, то подмножество добавляем в результат, а её строковое представление добавляем в хэш-сет added. В этом случае будет сложность проверки дубликата за O(1). (если не считать преобразование в строку, но это быстро).
Другое решение воспользоваться HashSet<List<int>>, но указать, как вычислять хэш-функцию и как проводить сравнение элементов.
HashSet<List<int>> result = new HashSet<List<int>>(EqualityComparer<List<int>>.Create((a, b) => a.SequenceEqual(b), (a) =>
{
var hashCode = 0;
foreach (var item in a)
{
hashCode += item.GetHashCode();
}
return hashCode;
}));Но этот вариант требует хорошей памяти документации C#, если решение писать не в IDE.
Сделаем рекурсивную функцию.
Она будет проходить по элементам массива. Как только она дошла до конца массива (это базовый случай рекурсии), у неё должно быть сформировано очередное подмножество ([], [1], [1,2] и т.д.), это подмножество преобразуется в строку путем конкатенации элементов через делиметр (запятую). Полученная строка ищется в хэш-сете, если она там есть, то просто выходим, если есть полученное множество добавляем в результат, а его строковое представление добавляем в хэш-сет.
Не в базовом случае функция будет добавлять элемент в подмножество, вызывать себя рекурсивно, потом будет удалять элемент из подмножества и снова вызывать себя рекурсивно. Таким образом, каждый элемент будет в одних множествах добавлен, в других - нет.
Итого, полный код такой:
public class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums)
{
HashSet<string> added = new();
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
Solve(0, nums, [], result, added);
return result.Select(v => (IList<int>)v).ToList();
}
public void Solve(int i, int[] nums, List<int> subset, IList<IList<int>> result, HashSet<string> added)
{
if (i == nums.Length)
{
var subsetString = string.Join(",", subset);
if (added.Contains(subsetString))
{
return;
}
added.Add(subsetString);
result.Add([.. subset]);
return;
}
subset.Add(nums[i]);
Solve(i + 1, nums, subset, result, added);
subset.RemoveAt(subset.Count - 1);
Solve(i + 1, nums, subset, result, added);
}
}Код работает. Решение на Литкоде проходит. Но можно ли ускорить?
Да.
Давайте посмотрим на такое множество:
1,1,1,1,2,2,2,2,3,3,3,3
мы увидим, что в ответе у нас должны быть комбинации
[], [3], [3,3], [3,3,3], [3,3,3,3], [2,3,3,3,3],[2,2,3,3,3,3], [2,2,2,3,3,3,3], [2,2,2,2,3,3,3,3],
[1,2,2,2,2,3,3,3,3]...[1,1,1,1,2,2,2,2,3,3,3,3], [1,3,3,3,3], [1,1,3,3,3,3],[1,1,1,3,3,3,3][1,1,1,13,3,3,3] и другие множества
Разобъем числа на группы одинаковых чисел.
Возьмем группу чисел 1,1,1,1.
Есть множества, где нет единицы.
Есть множества, где одна единица
Есть множества, где две единицы
Есть множества, где три единицы
Есть множества, где четыре единицы
Тоже самое с другими группами.
Поэтому перепишем функцию Solve таким образом.
Мы будем искать начало группы одинаковых чисел: [1,1,1,1], [2,2,2,2] и т.д.
Добавляем одно число из группы, вызываем функцию Solve рекурсивно.
Добавляем другое число из группы, вызываем функцию Solve рекурсивно.
и .т.д.
Потом удаляем группу и вызываем функцию Solve рекурсивно.
Нам уже не нужен HashSet.
Полный код такой:
public class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
Solve(0, nums, [], result);
return result;
}
public void Solve(int indexOfGroupStart, int[] nums, List<int> subset, IList<IList<int>> result)
{
if (indexOfGroupStart == nums.Length)
{
result.Add([..subset]);
return;
}
var groupNumber = nums[indexOfGroupStart];//число группы
var indexOfNextGroupStart = indexOfGroupStart + 1;//ищем начало следующей группы
for (; indexOfNextGroupStart < nums.Length; indexOfNextGroupStart++)
{
if (nums[indexOfNextGroupStart] != groupNumber)
{
break;
}
}
var groupSize = indexOfNextGroupStart - indexOfGroupStart;//количество элементов в группе
Solve(indexOfNextGroupStart, nums, subset, result);//запускаем Solve с пустой группой.
for (var i = 0; i < groupSize; i++)
{
subset.Add(groupNumber);//добавляем по одному
Solve(indexOfNextGroupStart, nums, subset, result);//запускаем Solve рекурсивно
}
subset.RemoveRange(subset.Count - groupSize, groupSize);//удаляем группу
}
}