← Static tasks

90. Subsets II

leetcode medium

#array#bit-manipulation#csharp#hash-table#leetcode#math#medium#sort#string

Task

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

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

Пример:

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#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;
    }
}

Java solution

matched/original
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;
    }
}

JavaScript solution

matched/original
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;
};

Python solution

matched/original
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

Go solution

matched/original
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
}

Explanation

Algorithm

1️⃣

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

2️⃣

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

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

3️⃣

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

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

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

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

Верните подмножества.

😎