Subsets

СреднеПоиск с возвратом Битовые операции

+10

Дан список nums различных целых чисел. Верните все его подмножества, включая пустое и всё множество целиком: для n значений получится 2^n подмножеств. Записывайте значения в каждом подмножестве в порядке возрастания, а сами подмножества располагайте в лексикографическом порядке: сравнивайте два подмножества поэлементно, решает первое различие, а подмножество, являющееся началом другого, ставьте перед ним. Для [1, 2] ответ — [[], [1], [1, 2], [2]].

Функция

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: значения, все разные, в любом порядке
Возвращаетinteger-2d-array: все подмножества, каждое из которых отсортировано по возрастанию, перечислены в лексикографическом порядке

Ограничения

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Все значения в nums различны.
nums могут идти в любом порядке.

Примеры

Ввод: nums = [3, 1, 2]
Вывод: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Пояснение: После сортировки получаем значения 1, 2, 3, а три значения дают 2^3 = 8 подмножеств. [1, 2] идёт перед [1, 2, 3], потому что является его началом, а [1, 2, 3] идёт перед [1, 3], потому что 2 меньше 3 на второй позиции.

Ввод: nums = [0]
Вывод: [[], [0]]
Пояснение: У одного значения есть два подмножества: пропустить его и получить [] или взять его и получить [0]. Пустое подмножество всегда идёт первым.

Ввод: nums = [5, -2]
Вывод: [[], [-2], [-2, 5], [5]]
Пояснение: Значения сортируются как -2 и 5, поэтому [-2, 5] записывается в таком порядке. Каждое подмножество, содержащее -2, идёт перед [5], потому что -2 меньше 5.

+13 скрытых тестов при отправке

Дополнительный вопрос

Можешь получить тот же список без рекурсии, строя каждое подмножество непосредственно из предыдущего?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Существует 2^n подмножеств, поэтому ни один метод не выполняет меньше работы, чем O(2^n). Настоящий вопрос заключается в том, как получить каждое подмножество ровно один раз и в требуемом порядке, не сортируя потом 1024 списка. Рекурсивный перебор с возвратом по отсортированным значениям, при котором записывается каждый узел дерева решений при входе в него, обходит подмножества точно в лексикографическом порядке.

Битовые маски, затем сортировка

Идея

Расположи отсортированные значения на позициях от 0 до n-1. Для каждой позиции подмножество указывает, входит она в него или нет, и именно это кодируют n бит числа. Поэтому числа от 0 до 2^n-1 соответствуют подмножествам: для [1, 2, 3] маска 5 — это двоичное число 101, установлены биты 0 и 2, и она обозначает [1, 3]. Маска 0 — пустое подмножество, а маска 7 — весь список.

Разные маски задают разные подмножества, и у каждого подмножества есть маска, поэтому цикл генерирует все 2^n подмножеств ровно по одному разу. Чтение битов от позиции 0 вверх по отсортированным значениям записывает каждое подмножество в порядке возрастания.

Маски идут не в том порядке, который требуется в задаче. Маска 1 — это [1], маска 2 — [2], а маска 3 — [1, 2], поэтому [2] окажется перед [1, 2]. Это исправляется сортировкой с компаратором, который сравнивает значения по очереди и ставит префикс раньше. Сортировка обходится дороже генерации: для 2^n подмножеств требуется примерно n × 2^n сравнений, и каждое сравнение считывает до n значений. При n = 10 это около 10^5 считываний — всё ещё быстро, но следующему подходу эта работа не нужна.

Алгоритм

Отсортируй nums так, чтобы каждый поднабор был упорядочен по возрастанию.
Для каждой маски от 0 до 2^n-1 собери значения в позициях, где установлен бит.
Отсортируй список поднаборов: в первой позиции, где два поднабора различаются, меньшим считается тот, в котором значение меньше; если один поднабор заканчивается раньше, он идёт первым.
Верни отсортированный список.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Возврат с возвратом: выбери, исследуй, отмени выбор

Идея

Представь подмножества в виде дерева. Корень — пустое подмножество. Ниже узла можно добавить любое значение, которое больше последнего добавленного. Для отсортированных значений [1, 2, 3] у корня есть дочерние узлы [1], [2] и [3]; у [1] — дочерние узлы [1, 2] и [1, 3]; у [1, 2] — дочерний узел [1, 2, 3]. Каждое подмножество встречается в этом дереве ровно один раз, потому что записать его в порядке возрастания можно только одним способом, и ответом является каждый узел, а не только листья.

Алгоритм с возвратом обходит дерево, используя один общий список — path. Чтобы перейти к дочернему узлу, нужно выбрать значение: добавить его в список. Затем нужно исследовать ветвь: выполнить рекурсивный вызов, и вспомогательная функция сохранит копию path в момент прибытия. После этого нужно отменить выбор: удалить значение, чтобы path снова соответствовал родительскому узлу и можно было проверить следующего соседа. Поскольку при входе записывается каждый узел, родитель всегда записывается раньше своих дочерних узлов.

Именно поэтому результат уже упорядочен лексикографически и сортировка не нужна. Дочерние узлы проверяются от наименьшего значения к наибольшему, и обход полностью завершает одну ветвь, прежде чем перейти к следующей. Для [1, 2, 3] он записывает [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: как в словаре, где префикс стоит перед вариантами с продолжением.

В дереве 2^n узлов, а копирование пути требует до n операций, поэтому время работы составляет O(n × 2^n) — столько же, сколько занимает сам ответ. Помимо результата, ты хранишь один путь и стек вызовов; глубина каждого из них не превышает n.

Алгоритм

Отсортируй значения.
Напиши explore(start). Сначала она добавляет копию path в результат.
Затем для каждого индекса i от start до конца: добавь values[i] в path (выбор), вызови explore(i+1) (исследование) и удали последнее значение (отмена выбора).
Вызови explore(0) с пустым путём и верни результат.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Ловушки и крайние случаи

Большинство неправильных ответов здесь связано с порядком или с тем, что один список используется совместно.

Добавление самого path, а не его копии. Тогда все элементы ссылаются на один и тот же список, который к концу обхода оказывается пустым, поэтому вы возвращаете 2^n копий [].
Забыть отсортировать nums. Для [3, 1, 2] дерево строит [3, 1], что не является возрастающим порядком, и обход больше не идет в лексикографическом порядке.
Сохранять результат только в листьях, как при построении перестановок. Каждый узел этого дерева — подмножество; если сохранять только пути, достигающие конца, будет возвращено слишком мало подмножеств.
Выполнять рекурсию с start+1 вместо i+1. Тогда после большего значения может идти меньшее или даже то же самое, и вы получите такие списки, как [3, 2] и [3, 3], которые не являются подмножествами в возрастающем порядке.
Использовать дерево включения или исключения (сначала выбрать значение 0, затем значение 1 и так далее) и сохранять результаты в листьях. Такой подход находит все 2^n подмножеств, но если сначала пробовать включение, полный список окажется первым, а если сначала пробовать исключение, [3] окажется перед [2]. Ни один из этих вариантов не дает лексикографического порядка.
Компаратор, который сначала сортирует по длине, задает порядок [], [1], [2], [3], [1, 2], который отличается от нужного.

Частые вопросы4

Сколько подмножеств имеет множество из n элементов?

2^n. Каждый элемент либо входит в подмножество, либо нет, независимо от остальных, поэтому количество вариантов перемножается: два для первого элемента, два для второго и так далее. Для трёх значений получается 8 подмножеств, а для десяти — 1024, включая пустое подмножество и всё множество.

Какова временная сложность задачи о подмножествах?

O(n × 2^n). Существует 2^n подмножеств, и на запись каждого из них может потребоваться до n шагов, поэтому даже возврат ответа требует столько же времени. Поиск с возвратом достигает этой границы и использует лишь O(n) дополнительной памяти. Генерация с помощью битовых масок происходит так же быстро, но последующая сортировка результата добавляет ещё один множитель n.

Использовать для подмножеств возврат с возвратом или битовые маски?

Битовые маски короткие, не требуют рекурсии и наглядно показывают выбор «включить или исключить» в виде битов. При использовании поиска с возвратом подмножества автоматически выводятся в лексикографическом порядке, и этот подход легко адаптировать к распространённым вариантам: пропускать повторяющиеся значения, выбирать только подмножества размера k или только те, сумма которых достигает заданного значения; в последнем случае можно заранее прекратить перебор ветви.

Как обрабатывать повторяющиеся значения в подмножествах?

Отсортируй значения, затем в цикле вспомогательной функции для возврата с возвратом пропускай значение, равное предыдущему на том же уровне: i > start и values[i] == values[i-1]. Первый экземпляр уже перебирает все подмножества, в которых он используется, поэтому ветвь-сосед, начинающаяся со второго экземпляра, лишь заново построила бы те же подмножества.

Python

def subsets(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [3, 1, 2]

Ожидается

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]