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

😎 Решение:

class Solution {
    private List<IList<int>> output = new List<IList<int>>();
    private int n, k;

    private void backtrack(int first, List<int> curr, int[] nums) {
        if (curr.Count == k) output.Add(new List<int>(curr));
        for (int i = first; i < n; ++i) {
            curr.Add(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.RemoveAt(curr.Count - 1);
        }
    }

    public IList<IList<int>> Subsets(int[] nums) {
        n = nums.Length;
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new List<int>(), nums);
        }

        return output;
    }
}

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