Условие задачи

Дан массив уникальных целых чисел nums. Необходимо вернуть все возможные подмножества чисел (множество всех подмножеств), которые можно получить из данного массива.

Примеры

Пример 1

Input: nums = [1,2,3]\ Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]\ Explanation:\ В данном примере возможны следующие подмножества:\ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Пример 2

Input: nums = [0]\ Output: [[],[0]]

Решение

Для решения данной задачи мы будем использовать рекурсивный алгоритм.

Шаги алгоритма

1. Создадим пустой список res, в котором мы будем хранить все подмножества.
2. Создадим функцию helper, которая будет принимать следующие аргументы:
   • текущий индекс idx
   • текущее подмножество subset
3. В теле функции helper:
   • добавим текущее подмножество в res
   • для каждого i, начиная с idx и до конца массива nums:
     • добавим nums[i] в subset
     • вызовем рекурсивно функцию helper с idx = i + 1 и subset
     • удалим последний элемент из subset
4. Вызовем функцию helper с начальными параметрами idx = 0 и subset = []

Пояснение с примером

Допустим, у нас есть массив nums = [1,2,3].\ После первого вызова функции helper с параметрами idx = 0 и subset = [] мы получим res = [[], [1], [2], [3]].\ Затем мы вызовем функцию helper с idx = 1 и subset = [1], и получим res = [[], [1], [2], [3], [1,2], [1,3]].\ Далее, мы вызовем функцию с idx = 2 и subset = [1,2] и получим res = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]].\ Теперь res содержит все возможные подмножества массива nums.

Код на Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def helper(idx, subset):
            res.append(subset)
            for i in range(idx, len(nums)):
                helper(i + 1, subset + [nums[i]])

        helper(0, [])
        return res