78. Subsets

Задача

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

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

/**
 * Генерирует все возможные подмножества (Power Set).
 *
 * Временная сложность: O(N * 2^N)
 * Обоснование:
 * 1. У массива из N элементов существует 2^N подмножеств.
 * 2. Для каждого из 2^N решений мы создаем копию массива `[...current]`.
 * 3. Копирование массива занимает O(N) (в среднем N/2).
 * 4. Итого: 2^N операций * O(N) копирование = O(N * 2^N).
 *
 * Пространственная сложность: O(N * 2^N)
 * Обоснование:
 * 1. Мы храним все 2^N подмножеств в массиве `result`.
 * 2. Суммарное количество элементов во всех подмножествах равно N * 2^(N-1).
 * 3. Стек рекурсии занимает O(N), но доминирует хранение результата.
 */
var subsets = function(nums) {
    const result = [];
 
    function backtrack(start, current) {
        // Операция копирования [...current] добавляет множитель N к сложности
        result.push([...current]);
 
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
 
    backtrack(0, []);
    return result;
};