В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример — 78 Subsets и 90 Subsets II.
Формулировка следующая — есть набор (множество) чисел, нужно составить все возможные подмножества, включая и пустое. Разница между двумя задачами лишь в том, что в первой (№78) задаче элементы множества уникальные, а во второй (№90) — нет. Но в обоих случаях требуется составить уникальные подмоножества.
Например, на входе [0, 1], результатом должно быть — [[], [0], [1], [0, 1]]
Если у нас N элементов, то мы должны составить структуру из N вложенных циклов, на каждой итерации решая будем ли добавлять элемент в текущий набор. В самом внутреннем цикле получившийся набор, мы добавим в результаты.
Такая структура, наверное, уместна для 2 — 3 элементов, но для N > 3, лучше воспользоваться рекурсивным методом.
Логика следующая:
- Мы начинаем с первого элемента множества и пустого набора.
- У нас есть выбор: выбранный элемент добавить в набор или не добавлять.
- В любом случае мы переходим к следующему элементу массива.
- Если мы просмотрели весь массив, то получившийся набор нужно добавить в результаты.
Посмотрим как это реализовано в коде (typescript):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
function subsets(nums: number[]): number[][] { // здесь собираем результат const res: number[][] = []; const iter = (n: number, chain: number[]) => { if (n >= nums.length) { // пункт 4 - массив закончился // добавляем результат res.push(chain) return; } // сначала мы не берём новый элемент в набор, iter(n + 1, [...chain]) // а затем берем, так у нас выходит просмотреть обе ветки chain.push(nums[n]) iter(n + 1, chain) // обратите внимание, что для первой ветки приходится клонировать набор, // а для второй - мы уже можем использовать как есть } // пункт 1 - начинаем с первого элемента в массиве и пустого набора iter(0, []) return res }; |
Наличие пустого набора обеспечивается тем, что мы можем отказаться от добавления новых элементов а набор, раз за разом передавая на следующую итерацию рекурсии начальный пустой набор.
Вторая задача (№90) идентична по методике перебора элементов, но нам нужно отсеять каким то образом дубли. В JavaScript с этой рутинной задачей хорошо справляются объекты Set и Map. Мы используем Map, т.к. нам требуется работать с объектами (массивами), а Set поможет вам только со скалярами.
Что бы не хранил в себе Map, но сравнивает он значения также по ключу, потому мы будем сопоставлять каждому набору chain — скаляр. Можно придумать разные варианты, например:
|
1 2 3 |
chain.join('/') // или JSON.stringify(chain) |
Давайте разбирать код:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
function subsetsWithDup(nums: number[]): number[][] { const res: Map<string,number[]> = new Map(); // массив предварительно можно упорядочить // тогда не нужно будет выполнять сортировку перед // созданием ключа для объекта Map nums.sort((a, b) => a - b) const iter = (n: number, chain: number[]) => { if (n >= nums.length) { // сохраняем очередной вариант res.set(chain.join('/'), chain) return; } iter(n + 1, [...chain]) chain.push(nums[n]) iter(n + 1, chain) } iter(0, []) // извлекаем набор значений из Map return [...res.values()] }; |