public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(new ArrayList<Integer>());
int begin = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0  nums[i] != nums[i  1]) begin = 0;
int size = result.size();
for(int j = begin; j < size; j++){
List<Integer> cur = new ArrayList<Integer>(result.get(j));
cur.add(nums[i]);
result.add(cur);
}
begin = size;
}
return result;
}
Share my 2ms java iteration solution (very simple and short)


public IList<IList<int>> SubsetsWithDup(int[] nums) { List<IList<int>> res = new List<IList<int>>(); res.Add(new List<int>()); // [] Array.Sort(nums); int dupStart = 1; for (int i=0; i<nums.Length; i++){ int count = res.Count, start=0; if (i>0 && nums[i]==nums[i1]){ // duplicate start = dupStart; } for (int j=start; j<count; j++){ List<int> seq = new List<int>(res[j]); seq.Add(nums[i]); res.Add(seq); } dupStart = count; } return res; }
Similar idea here. Not sure why there's a tag of backtracking, it looks more like DP.