C++ solution and explanation


  • 177
    M

    To solve this problem, it is helpful to first think how many subsets are there. If there is no duplicate element, the answer is simply 2^n, where n is the number of elements. This is because you have two choices for each element, either putting it into the subset or not. So all subsets for this no-duplicate set can be easily constructed:
    num of subset

    • (1 to 2^0) empty set is the first subset
    • (2^0+1 to 2^1) add the first element into subset from (1)
    • (2^1+1 to 2^2) add the second element into subset (1 to 2^1)
    • (2^2+1 to 2^3) add the third element into subset (1 to 2^2)
    • ....
    • (2^(n-1)+1 to 2^n) add the nth element into subset(1 to 2^(n-1))

    Then how many subsets are there if there are duplicate elements? We can treat duplicate element as a spacial element. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset. Therefore, we are given an array (a1, a2, a3, ..., an) with each of them appearing (k1, k2, k3, ..., kn) times, the number of subset is (k1+1)(k2+1)...(kn+1). We can easily see how to write down all the subsets similar to the approach above.

        class Solution {
    public:
        vector<vector<int> > subsetsWithDup(vector<int> &S) {
            vector<vector<int> > totalset = {{}};
            sort(S.begin(),S.end());
            for(int i=0; i<S.size();){
                int count = 0; // num of elements are the same
                while(count + i<S.size() && S[count+i]==S[i])  count++;
                int previousN = totalset.size();
                for(int k=0; k<previousN; k++){
                    vector<int> instance = totalset[k];
                    for(int j=0; j<count; j++){
                        instance.push_back(S[i]);
                        totalset.push_back(instance);
                    }
                }
                i += count;
            }
            return totalset;
            }
    };

  • 0
    J

    very easy to understand.


  • 0

    Welcome @mathsam! +1 and thanks for writing an excellent explanation.


  • 0
    Z

    excellent solution!


  • 0
    L

    Hello, I got a question. I just did as your algorithm. The only different is that I use

    ...
    for(int k=0; k<previousN; k++){
    ...

    instead of

    ...
    int previousN = totalset.size();
    for(int k=0; k<previousN; k++){
    ...

    And then I got a MLE error. Could anyone help me explain why?


  • 23
    H

    Thanks for the sharing! Here is the Java version.

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] num) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> empty = new ArrayList<Integer>();
            result.add(empty);
            Arrays.sort(num);
            
            for (int i = 0; i < num.length; i++) {
                int dupCount = 0;
                while( ((i+1) < num.length) && num[i+1] == num[i]) {
                    dupCount++;
                    i++;
                }
                int prevNum = result.size();
                for (int j = 0; j < prevNum; j++) {
                    List<Integer> element = new ArrayList<Integer>(result.get(j));
                    for (int t = 0; t <= dupCount; t++) {
                        element.add(num[i]);
                        result.add(new ArrayList<Integer>(element));
                    }
                }
            }
            return result;
        }
    }
    

    I have a question regarding the link of code for(int j=0; j<count; j++) in C++ version. if duplication count is zero, how do we add the new subset to the total set? I am thinking at least we need to jump into for loop at least one time even for the non-duplicate set .


  • 0

    Inspired by this answer, here is my implementation in JavaScript.

    /**
     * @param {number[]} S
     * @return {number[][]}
     */
    var subsetsWithDup = function(S) {
      
      // Make sure the S is sorted   
      S.sort();
      
      var subsets = [[]], 
          subset;
       
      var num, dupCount, prevSubsetSize;
      for ( var i = 0; i < S.length; i++ ) {
        
        num = S[i];
        dupCount = 1;
        // Check whether there is a next element ( i+1 < S.length )
        // and then check whether cururent element equals to the next elements
        while ( i+1 < S.length && S[i] == S[i+1] ) {
          dupCount += 1; 
          i++;
        }
        
        prevSubsetSize = subsets.length;
        for ( var j = 0; j < prevSubsetSize; j++ ) {
           subset = copyArray( subsets[j] );
           for ( var k = 1; k <= dupCount; k++ ) {
              if ( k > 0 ) { subset.push(num); }
              subsets.push( 
                  copyArray(subset).sort(function(a,b){return a-b}) 
              ); // by default, sort function sort array item alphabetically
           }
         }
       }
       
       return subsets;
        
    };
    
    // Helper
    var copyArray = function(array) {
        return array.slice( 0, array.length );
    }
    

  • 0
    A

    Have you figured out why?


  • 0
    This post is deleted!

  • 0
    I

    Since the length of totalset changes(increases) in for loop [totalset.add(subset)]


  • 1

    The count in the above C++ code has different meaning with the dupCount in your Java code. The count in the C++ code means the number of elements that are the same. If no duplicate exists, count = 1 while in your code dupCount = 0 if no duplicate.


  • 1

    I guess you use code like for (int k = 0; k < totalset.size(); k++), right? Since totalset keeps growing, this for loop will not terminate and your code will keeping running until there is no memory available :-) And this process is very fast so you will see MLE instead of TLE :-)


  • 0

    Since you initialize var k = 1, why do you still check if (k > 0) inside the for loop?


  • 0

    Damn clever solution! The greatest aspect of this idea is that it can be used to solve both Subsets and Subsets II. In fact, I guess it may also be extended to other subset-related problems :-)


  • 0
    R

    can someone explain what he has written in a clear way ?


  • 1
    F

    good solution! I thought the same way, but the order of my two most inner loops are opposite, and it still make sense.

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    	vector<vector<int> > totalset = {{}};
    	sort(nums.begin(), nums.end());
    	for (int i = 0; i<nums.size();) {
    		int count = 0; // num of elements are the same
    		while (count + i<nums.size() && nums[count + i] == nums[i])  count++;
    		int previousN = totalset.size();
    		vector<int> tmp;
    		for (int c = 0; c < count; c++) {
    			tmp.push_back(nums[i]);
    			for (int j = 0; j < previousN; j++) {
    				totalset.push_back(totalset[j]);
    				totalset.back().insert(totalset.back().end(), tmp.begin(), tmp.end());
    			}
    		}
    		i += count;
    	}
    	return totalset;
    }

  • 0
    Z

    actually, we can init count = 1 to reduce one time loop.


  • 0
    M

    shouldn't count = 1 instead?


  • 0
    R

    bit manipulation can solve this too
    How to escape the duplicate? easy! use a sign to mark it:
    this is where this state from "if(j>0&&nums[j]==nums[j-1]&&(i>>(j-1)&1)==0)"
    'nums[j] == nums[j-1]' means the array has a duplicate;
    'i>>(j-1)&1)==0' means the bit manipulation is doing with the duplicate bits!

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i =0; i<(1<<length); i++){
            List<Integer> l = new LinkedList<Integer>();
            boolean duplicate = false;
            for(int j =0; j<length; j++){
                if( (i&(1<<j))!=0 ){
                    if(j>0&&nums[j]==nums[j-1]&&(i>>(j-1)&1)==0){
                        duplicate = true;
                        break;
                    }
                    l.add(nums[j]);
                }
            }
            if( duplicate ==false )
                list.add(l);
        }
        return list;
    }

  • 0
    E

    Brilliant!!!


Log in to reply
 

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