Simple iterative solution


  • 100
    Y

    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;
    }

  • 0
    K

    Great and elegant solution!


  • 0
    L

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


  • 0
    T

    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.


  • 0
    W

    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++;
    }
    int addCnt = res.size();
    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;
    }
    };


  • 30
    B

    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<>();
      ret.add(new ArrayList<Integer>());
    
      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));
          temp.add(num[i]);
          ret.add(temp);
        }
      }
      return ret;
    }

  • 0
    S

    That's brilliant!


  • 0

    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;
        } 
    };

  • 0
    O

    Had the same idea, Cheers

    public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList();
            ans.add(new ArrayList()); // add []
            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));
                        cur.add(nums[i]);
                        ans.add(cur);
                    }
                prev = size;
            }
            return ans;
        }

  • 0

    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
            allSets.Add(new List<int>());
            
            // 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);
                    clone.Add(nums[i]);
                    currSets.Add(clone);
                }
                
                allSets.AddRange(currSets);
                prevSets = currSets;
            }
            
            return allSets;
        }
    

  • -1
    C

    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>();
                l.add(l3);
                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>();
                l2.addAll(l.get(j));
                l2.add(nums[index]);
                lCopy.add(l2);
            }
            l.addAll(lCopy);
            return lCopy.size();
        }
    }
    

  • 0

    @yuruofeifei

    So insightful.


  • 0
    G

    The usage of parameter size is pretty interesting!


  • 0
    M

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


Log in to reply
 

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