Simple iterative solution

• If we want to insert an element which is a dup, we can only insert it after the newly inserted elements from last step.

``````vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int>> ret = {{}};
int size = 0, startIndex = 0;
for (int i = 0; i < S.size(); i++) {
startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;
size = ret.size();
for (int j = startIndex; j < size; j++) {
vector<int> temp = ret[j];
temp.push_back(S[i]);
ret.push_back(temp);
}
}
return ret;
}``````

• Great and elegant solution!

• Great Idea, this solution is hard to find out, I'm debuging step by step, and finally understand it, cool.

• startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;
The above row is used to eliminate duplication.
The inner for loop is to invert a new vector<int> iteratively, and every time when generation the new vector<int>, which is variable temp, just the vector<int>s already in ret, then just insert with a new element into each of them. Then insert the new temp into ret.

• My first solution is almost the same. But there is unnecessary coping at sentence"vector<int> temp = ret[j];"(about 'startIndex' length). My second solution is faster.
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S)
{
sort(S.begin(), S.end());
vector<vector<int> > res(1, vector<int>());
for(int i = 0; i < S.size(); i++)
{
int sameCnt = 1;
while(i + 1 < S.size() && S[i + 1] == S[i])
{
sameCnt++;
i++;
}
for(int j = 0; j < addCnt; j++)
{
vector<int> tmp(res[j]);
for(int k = 0; k < sameCnt; k++)
{
tmp.push_back(S[i]);
res.push_back(tmp);
}
}
}
return res;
}
};

• Java version of the elegant solution. you are welcome!

``````public List<List<Integer>> subsetsWithDup(int[] num) {
Arrays.sort(num);
List<List<Integer>> ret = new ArrayList<>();

int size = 0, startIndex;
for(int i = 0; i < num.length; i++) {
startIndex = (i >= 1 && num[i] == num[i - 1]) ? size : 0;
size = ret.size();
for(int j = startIndex; j < size; j++) {
List<Integer> temp = new ArrayList<>(ret.get(j));
}
}
return ret;
}``````

• That's brilliant!

• A clever idea! I have rewritten the code below, with some minor changes in the addition of a new subset.

``````class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int> > res(1, vector<int>());
int sz = 0, n = nums.size();
for (int i = 0; i < n; i++) {
int idx = ((i >= 1 && nums[i] == nums[i - 1]) ? sz : 0);
sz = res.size();
for (int j = idx; j < sz; j++) {
res.push_back(res[j]);
res.back().push_back(nums[i]);
}
}
return res;
}
};``````

• Had the same idea, Cheers

``````public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList();
for (int i = 0, prev = 0; i < nums.length; i++) {
int size = ans.size();
for (int j = (i == 0 || nums[i] != nums[i - 1]) ? 0 : prev; j < size; j++) {
List<Integer> cur = new ArrayList(ans.get(j));
}
prev = size;
}
return ans;
}``````

• same idea here in C#, just using a temp set (previous iteration results) in place of the start index. Have to say the start index is better but this is what I came up with.

``````    public IList<IList<int>> SubsetsWithDup(int[] nums)
{
List<IList<int>> allSets = new List<IList<int>>();
List<IList<int>> prevSets = null;

// seed with empty set

// sort input to allow for checking if previous element is a duplicate
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
// capture current sets in separate collection in order to reuse only these on next iteration if dupe
List<IList<int>> currSets = new List<IList<int>>();

// the sets to clone on this iteration for no dupe is all sets, for dupe will be previous sets
List<IList<int>> fieldSets = (i == 0 || nums[i-1] != nums[i]) ? allSets : prevSets;

// clone all sets determined by the field logic and add this element to each of the clonded sets
foreach (IList<int> f in fieldSets)
{
IList<int> clone = new List<int>(f);
}

prevSets = currSets;
}

return allSets;
}
``````

• Java recursive solution with same concept. Helper method is returning the number of lists added by the previous element. Also We are updating the list as we recurse.

``````public class Solution {

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> l = new ArrayList<List<Integer>>();
Arrays.sort(nums);
helper(l, nums, nums.length-1);
return l;
}

public int helper(List<List<Integer>> l, int[] nums, int index){
if(index<0){
List<Integer> l3=new ArrayList<Integer>();
return 0;
}
int previousSize=helper(l, nums, index-1);
int startIndex = ((index > 0) && nums[index] == nums[index - 1] ) ? (l.size()-previousSize) : 0;
List<List<Integer>> lCopy = new ArrayList<List<Integer>>();
for(int j=startIndex;j<l.size();j++){
List<Integer> l2=new ArrayList<Integer>();
}
return lCopy.size();
}
}
``````

• @yuruofeifei

So insightful.

• The usage of parameter size is pretty interesting!

• This is the simplest, most elegant solution. Should be top voted.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.