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

В теории программирования большой класс задач связан с перебором подмножеств, и на 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 — скаляр. Можно придумать разные варианты, например:

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

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

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

Классическая задача о размене монет

Январь 24, 2023 г.

Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет. Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, ...

Читать

Задача - число островов

Март 25, 2023 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать

 

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

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



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