Алгоритмы: Power Set

В этом сообщении объясняется решение проблемы с настройкой мощности.

Постановка задачи

Учитывая набор различных целых чисел, nums, верните все возможные подмножества (набор мощности).

Пример 1:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Вот вопрос: Leetcode link.

Само собой разумеется, что сначала вам следует попробовать решить эту проблему.

Код

Вот решение проблемы (код Python), за кодом следует объяснение.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(level, initial, combination):
            '''backtracking function to generate
            power set'''
            
            # base case
            # if level == combination length, add
            # to the power set solution
            if level == len(combination):
                # add a copy of the combination
                # to the power set
                solution.append(combination[:])
                return
            # iterate over array to backtrack
            for i in range(initial, n):
                # add the element to combination
                combination.append(nums[i])
                # recurse for next element to complete
                # combination
                backtrack(level, i+1, combination)
                # backtrack
                combination.pop()
        n = len(nums)
        solution = []
        
        # iterate levels fro 0 to len(nums)
        # generate all subsets of length level from
        # 0 to len(nums)
        for level in range(n+1):
            backtrack(level, 0, [])
        return solution

Интуиция

Ключевым моментом в этой проблеме является разработка стратегии рекурсии и генерации всех комбинаций.

Давайте разберем проблему на:

• генерировать все комбинации длины 0 (пустой набор)
• генерировать все комбинации длины 1 (отдельные элементы)
• генерировать все комбинации длины 2

… И так далее до длины данного массива.

Это дает нам скелет нашего кода: он должен перебирать массивы по длине.

   # iterate levels fro 0 to len(nums) generate all subsets 
   # of length level from 0 to len(nums)
   for level in range(n+1):
       # generate all combinations of length level

Вот как мы визуализируем скелет нашего кода:

• Мы перебираем все возможные длины данного массива
• использовать рекурсивную функцию backtrack, которая генерирует комбинации определенной длины
• на каждой итерации backtrack будет генерировать все комбинации, которые мы добавляем в массив solution

def backtrack(level, initial, combination)
    # base case
    if level == len(combination):
    # add a copy of the combination to the power set
    solution.append(combination[:])
    return
        
    for i in range(initial, n):
        combination.append(nums[i])
        backtrack(level, i+1, combination)
        combination.pop()

Как определить сигнатуру backtrack рекурсивной функции?

• backtrack потребуется начальный индекс initial в данном массиве, используемом в качестве опорного элемента
• поскольку мы генерируем комбинации заданной длины, имеет смысл передать level генерируемой комбинации (уровень здесь - длина комбинаций от 0 до n)
• при каждом рекурсивном вызове создается комбинация, поэтому имеет смысл передавать массив combination в каждом вызове

Итак, у нас есть 3 параметра: backtrack(level, initial, combination)

Реализация backtrackrecursive функции:

• каждая рекурсивная функция имеет базовый случай, для этой функции, если длина комбинации, переданной в функцию, равна level, мы добавляем к массиву solution и возвращаем
• перебирать заданный массив от initial до общей длины:
  - добавить элемент i-th в массив combination
  - вызвать backtrack(level, i+1, combination): increment i, поскольку элемент ith уже был рассмотрен. Это запускает рекурсивный вызов до тех пор, пока не будут созданы все комбинации требуемой длины
  - удалить вставленный элемент, чтобы вернуться к предыдущей комбинации

Заключение

Мы столкнулись с важной концепциейbacktracking. Требуется практика, чтобы выработать интуицию для решения проблем с возвратом. Уловка, которую я нашел, заключается в следующем:

• развивать способность формировать рекурсивные решения заданных проблем
• идентифицировать функциональные сигнатуры рекурсивных функций
• определить базовые случаи
• определить состояние (решения или пространства дерева рекурсии), в котором должен быть выполнен возврат: после достижения решения или при достижении недопустимого решения. Следует помнить о двух важных вещах:
  - почему вернуться (с какой оптимизацией это помогает)
  - когда отступать (на в какую точку или условие мы возвращаемся)
  - где возвращаться (какое состояние решения мы достигаем после возврата)

Вот несколько ресурсов для изучения обратного отслеживания: