Задача о подмножествах

В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример — 78 Subsets и 90 Subsets II.

Формулировка следующая — есть набор (множество) чисел, нужно составить все возможные подмножества, включая и пустое. Разница между двумя задачами лишь в том, что в первой (№78) задаче элементы множества уникальные, а во второй (№90) — нет. Но в обоих случаях требуется составить уникальные подмоножества.

Например, на входе [0, 1], результатом должно быть — [[], [0], [1], [0, 1]]

Если у нас N элементов, то мы должны составить структуру из N вложенных циклов, на каждой итерации решая будем ли добавлять элемент в текущий набор. В самом внутреннем цикле получившийся набор, мы добавим в результаты.

Такая структура, наверное, уместна для 2 — 3 элементов, но для N > 3, лучше воспользоваться рекурсивным методом.

Логика следующая:

  1. Мы начинаем с первого элемента множества и пустого набора.
  2. У нас есть выбор: выбранный элемент добавить в набор или не добавлять.
  3. В любом случае мы переходим к следующему элементу массива.
  4. Если мы просмотрели весь массив, то получившийся набор нужно добавить в результаты.

Посмотрим как это реализовано в коде (typescript):

Наличие пустого набора обеспечивается тем, что мы можем отказаться от добавления новых элементов а набор, раз за разом передавая на следующую итерацию рекурсии начальный пустой набор.

Вторая задача (№90) идентична по методике перебора элементов, но нам нужно отсеять каким то образом дубли. В JavaScript с этой рутинной задачей хорошо справляются объекты Set и Map. Мы используем Map, т.к. нам требуется работать с объектами (массивами), а Set поможет вам только со скалярами.

Что бы не хранил в себе Map, но сравнивает он значения также по ключу, потому мы будем сопоставлять каждому набору chain — скаляр. Можно придумать разные варианты, например:

Давайте разбирать код:

Написать комментарий

Мало букафф? Читайте есчо !

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

 

Комментарии к «Задача о подмножествах»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: