Задача: 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.

😎 Решение:

function subsets($nums) {
    $output = [];
    $n = count($nums);
    
    function backtrack($first, $curr, $k, &$output, $nums, $n) {
        if (count($curr) == $k) {
            $output[] = $curr;
            return;
        }
        for ($i = $first; $i < $n; $i++) {
            $curr[] = $nums[$i];
            backtrack($i + 1, $curr, $k, $output, $nums, $n);
            array_pop($curr);
        }
    }
    
    for ($k = 0; $k <= $n; $k++) {
        backtrack(0, [], $k, $output, $nums, $n);
    }
    return $output;
}

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