Algorithm
Problem Name: 90. Subsets II
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int **p;
int *csz;
int psz;
int pn;
} res_t;
void add2res(res_t *res, int *buff, int d) {
if (d) {
int *tmp = malloc(d * sizeof(int));
//assert(tmp);
memcpy(tmp, buff, d * sizeof(int));
res->p[res->pn] = tmp;
} else {
res->p[res->pn] = NULL;
}
res->csz[res->pn ++] = d;
}
void bt(int *nums, int sz, int start, res_t *res, int *buff, int d) {
int i;
add2res(res, buff, d);
for (i = start; i < sz; i ++) {
if (i > start && nums[i] == nums[i - 1]) continue;
buff[d] = nums[i];
bt(nums, sz, i + 1, res, buff, d + 1);
}
}
int cmp(const void *a, const void *b) {
int x = *(int *)a, y = *(int *)b;
return x < y ? -1 :
x > y ? 1 : 0;
}
int** subsetsWithDup(int* nums, int numsSize, int** columnSizes, int* returnSize) {
res_t res = { 0 };
int *buff, i;
res.psz = 1 << numsSize;
res.p = malloc(res.psz * sizeof(int *));
res.csz = malloc(res.psz * sizeof(int));
//assert(res.p && res.csz);
buff = malloc(numsSize * sizeof(int));
//assert(buff);
qsort(nums, numsSize, sizeof(int), cmp);
bt(nums, numsSize, 0, &res, buff, 0);
free(buff);
*columnSizes = res.csz;
*returnSize = res.pn;
return res.p;
}
Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector> subsetsWithDup(vector& nums) {
vector>res;
backtrack(res, nums, 0, vector());
return res;
}
private:
void backtrack(vector>& res, vector& nums, int pos, vectorcomb){
if(pos >= nums.size()){
for(auto x: res) if(isEqual(x, comb)) return;
res.push_back(comb);
return;
}
backtrack(res, nums, pos + 1, comb);
comb.push_back(nums[pos]);
backtrack(res, nums, pos + 1, comb);
}
bool isEqual(vector& v1, vector& v2){
if(v1.size() != v2.size()) return false;
unordered_mapm;
for(auto x: v1) m[x]++;
for(auto x: v2) if(--m[x] < 0) return false;
return true;
}
};
Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List> subsetsWithDup(int[] nums) {
List> ans = new ArrayList<>();
List curr = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
helper(nums, 0, n, ans, curr);
return new ArrayList<>(ans);
}
private void helper(int[] nums, int idx, int n, List> ans, List curr) {
ans.add(new ArrayList<>(curr));
if (idx >= n) {
return;
}
for (int i = idx; i < n; i++) {
if (i > idx && nums[i] == nums[i - 1]) {
continue;
}
curr.add(nums[i]);
helper(nums, i + 1, n, ans, curr);
curr.remove(curr.size() - 1);
}
Input
nums = [0]
Output
[[],[0]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const res = [];
bt(res, nums, [], 0);
return res;
};
function bt(res, nums, arr, start) {
res.push(arr.slice(0));
for (let i = start; i < nums.length; i++) {
if (i === start || nums[i] !== nums[i - 1]) {
arr.push(nums[i]);
bt(res, nums, arr, i + 1);
arr.pop();
}
}
}
Input
nums = [0]
Output
[[],[0]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
from itertools import combinations as cb
res, dic = [], set()
for i in range(len(nums) + 1):
for item in cb(nums, i):
item = tuple(sorted(item))
if item not in dic:
dic.add(item)
res.append(item)
return res
Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _090_Subsets2
{
public IList> SubsetsWithDup(int[] nums)
{
var results = new List>() { new List() };
if (nums.Length == 0) return results;
Array.Sort(nums);
results.Add(new List() { nums[0] });
IList> lastAdded = new List>() { new List() { nums[0] } };
for (var i = 1; i < nums.Length; i++)
{
var result = new List>();
if (nums[i] == nums[i - 1])
{
foreach (var item in lastAdded)
{
var newItem = new List(item);
newItem.Add(nums[i]);
result.Add(newItem);
}
}
else
{
foreach (var item in results)
{
var newItem = new List(item);
newItem.Add(nums[i]);
result.Add(newItem);
}
}
results.AddRange(result);
lastAdded = result;
}
return results;
}
}
}
Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]