90. Subsets II
Дан 배열 целых чисел nums, который может содержать повторяющиеся elementы. return все возможные подмножества (степенной набор).
Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке.
예제:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
C# 해법
매칭됨/원본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++ 해법
자동 초안, 제출 전 검토#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 해법
매칭됨/원본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 해법
매칭됨/원본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 해법
매칭됨/원본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 subsetsGo 해법
매칭됨/원본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️⃣
Отсортируйте 배열 nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты.
2️⃣
Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n.
Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества.
3️⃣
Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию elementов в 배열е nums, которые присутствуют в текущем подмножестве.
Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества.
Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode.
Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen.
return подмножества.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.