78. Subsets

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;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
    private List<vector<int>> output = new List<vector<int>>();
    private int n, k;
    private void backtrack(int first, List<int> curr, vector<int>& nums) {
        if (curr.size() == k) output.push_back(new List<int>(curr));
        for (int i = first; i < n; ++i) {
            curr.push_back(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.RemoveAt(curr.size() - 1);
        }
    }
    public IList<vector<int>> Subsets(vector<int>& nums) {
        n = nums.size();
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new List<int>(), nums);
        }
        return output;
    }
}

class Solution {

    List<List<Integer>> output = new ArrayList();
    int n, k;

    public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
        if (curr.size() == k) {
            output.add(new ArrayList(curr));
            return;
        }
        for (int i = first; i < n; ++i) {
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        for (k = 0; k < n + 1; ++k) {
            backtrack(0, new ArrayList<Integer>(), nums);
        }
        return output;
    }
}

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;
};

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first=0, curr=[]):
            if len(curr) == k:
                output.append(curr[:])
                return
            for i in range(first, n):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

func subsets(nums []int) [][]int {
  n := len(nums)
  var output [][]int
  var curr []int
  var backtrack func(int, int)
  backtrack = func(first int, k int) {
    if len(curr) == k {
      output = append(output, append([]int(nil), curr...))
      return
    }
    for i := first; i < n; i++ {
      curr = append(curr, nums[i])
      backtrack(i+1, k)
      curr = curr[:len(curr)-1]
    }
  }
  for k := 0; k < n+1; k++ {
    backtrack(0, k)
  }
  return output
}

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎