Задача: 78. Subsets
Сложность: medium

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

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

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

👨‍💻 Алгоритм:

1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

var subsets = function (nums) {
    let output = [];
    let n = nums.length;
    function backtrack(first = 0, curr = [], k) {
        if (curr.length == k) {
            output.push([...curr]);
            return;
        }
        for (let i = first; i < n; i++) {
            curr.push(nums[i]);
            backtrack(i + 1, curr, k);
            curr.pop();
        }
    }
    for (let k = 0; k < n + 1; k++) {
        backtrack(0, [], k);
    }
    return output;
};

Ставь 👍 и забирай 📚 Базу знаний