90. Subsets II

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        IList<IList<int>> subsets = new List<IList<int>>();
        int n = nums.Length;
        Array.Sort(nums);
        int maxNumberOfSubsets = (int)Math.Pow(2, n);
        HashSet<string> seen = new HashSet<string>();
        for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
            List<int> currentSubset = new List<int>();
            StringBuilder hashcode = new StringBuilder();
            for (int j = 0; j < n; j++) {
                int mask = 1 << j;
                int isSet = mask & subsetIndex;
                if (isSet != 0) {
                    currentSubset.Add(nums[j]);
                    hashcode.Append(nums[j]).Append(",");
                }
            }
            if (!seen.Contains(hashcode.ToString())) {
                seen.Add(hashcode.ToString());
                subsets.Add(currentSubset);
            }
        }
        return subsets;
    }
}

#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 {
public:
    public IList<vector<int>> SubsetsWithDup(vector<int>& nums) {
        IList<vector<int>> subsets = new List<vector<int>>();
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int maxNumberOfSubsets = (int)Math.Pow(2, n);
        HashSet<string> seen = new HashSet<string>();
        for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
            List<int> currentSubset = new List<int>();
            StringBuilder hashcode = new StringBuilder();
            for (int j = 0; j < n; j++) {
                int mask = 1 << j;
                int isSet = mask & subsetIndex;
                if (isSet != 0) {
                    currentSubset.push_back(nums[j]);
                    hashcode.Append(nums[j]).Append(",");
                }
            }
            if (!seen.Contains(hashcode.ToString())) {
                seen.push_back(hashcode.ToString());
                subsets.push_back(currentSubset);
            }
        }
        return subsets;
    }
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList();
        int n = nums.length;
        Arrays.sort(nums);
        int maxNumberOfSubsets = (int) Math.pow(2, n);
        Set<String> seen = new HashSet<>();

        for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
            List<Integer> currentSubset = new ArrayList();
            StringBuilder hashcode = new StringBuilder();
            for (int j = 0; j < n; j++) {
                int mask = 1 << j;
                int isSet = mask & subsetIndex;
                if (isSet != 0) {
                    currentSubset.add(nums[j]);
                    hashcode.append(nums[j]).append(",");
                }
            }
            if (!seen.contains(hashcode.toString())) {
                seen.add(hashcode.toString());
                subsets.add(currentSubset);
            }
        }

        return subsets;
    }
}

var subsetsWithDup = function (nums) {
    var n = nums.length;
    nums.sort();
    var subsets = [];
    var seen = new Set();
    var maxNumberOfSubsets = Math.pow(2, n);
    for (var subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {
        var currentSubset = [];
        var hashcode = "";
        for (var j = 0; j < n; j++) {
            var mask = 1 << j;
            var isSet = mask & subsetIndex;
            if (isSet != 0) {
                currentSubset.push(nums[j]);
                hashcode += nums[j] + ",";
            }
        }
        if (!seen.has(hashcode)) {
            subsets.push(currentSubset);
            seen.add(hashcode);
        }
    }
    return subsets;
};

class Solution:
    def subsetsWithDup(self, nums):
        n = len(nums)
        nums.sort()
        maxNumberOfSubsets = 2**n
        seen = set()
        subsets = []
        for subsetIndex in range(maxNumberOfSubsets):
            currentSubset = []
            hashcode = ""
            for j in range(n):
                mask = 2**j
                isSet = mask & subsetIndex
                if isSet != 0:
                    currentSubset.append(nums[j])
                    hashcode += str(nums[j]) + ","
            if hashcode not in seen:
                subsets.append(currentSubset)
                seen.add(hashcode)
        return subsets

func subsetsWithDup(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    subsets := make([][]int, 0)
    maxNumberOfSubsets := 1 << n
    seen := make(map[string]bool)
    for subsetIndex := 0; subsetIndex < maxNumberOfSubsets; subsetIndex++ {
        currentSubset := make([]int, 0)
        hashcode := ""
        for j := 0; j < n; j++ {
            mask := 1 << j
            isSet := mask & subsetIndex
            if isSet != 0 {
                currentSubset = append(currentSubset, nums[j])
                hashcode += strconv.Itoa(nums[j]) + ","
            }
        }
        if _, ok := seen[hashcode]; !ok {
            subsets = append(subsets, currentSubset)
            seen[hashcode] = true
        }
    }
    return subsets
}

Algorithm

1️⃣

Отсортируйте array nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты.

2️⃣

Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n.

Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества.

3️⃣

Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию elementов в arrayе nums, которые присутствуют в текущем подмножестве.

Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества.

Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode.

Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen.

return подмножества.

😎