How to adapt subsets I solution to subsets II problem?


  • 1
    C

    Find a way to adapt subset I solution to subsets II problem.


  • 0

    Thanks for posting. Could you please transform this into a question? I suggest something like "How to adapt this Subsets I solution to Subsets II problem?", then you can post your answer below. Yes, you may answer your own question :)


  • 29
    C

    Here is the answer I found from old discuss forum for SUBSETS I:

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > v(1);
        for(int i = 0; i < S.size(); ++i) {
            int j = v.size();
            while(j-- > 0) {
                v.push_back(v[j]);
                v.back().push_back(S[i]);
            }
        }
        return v;
    }
    

    The above answer just need small modification to handle problem SUBSETS II.

    1. if a number from S is the first one of the numbers with the same value, it can be used to extend all previous subsets and create new non-duplicate subsets.

    2. if a number from S is a duplicated number of some value, it cannot be used to extend all previous subsets. Only part of them. The idea is that this number should help make some different subsets than its predecessor. So it only needs to extend subsets which contains its predecessor.

    e.g. [ 1 2 2]

    [ ]

    [1]

    [1 2] [2]

    // now predecessor is the first 2, we will only extend subsets which already contains the first 2, go no further...

    [1 2 2] [2 2]

        //answer for SUBSETS II
        vector<vector<int> > subsetsWithDup(vector<int> &S) {
            sort(S.begin(), S.end());
            vector<vector<int>> result(1);
            int oldval=S[0];
            int oldj=0;
            for(int i=0; i<S.size(); i++){
                int temp=oldj;
                if(S[i]!=oldval){
                    oldval=S[i]; temp=0;
                }
                int j=result.size();
                oldj=j;
                while(j-->temp){
                    //note temp here help avoid creating duplicate subsets
                    result.push_back(result[j]);
                    result.back().push_back(S[i]);
                }
            }
            return result;
        } 

  • 0
    C

    Hi coder, where can we see solutions of others in this new discuss forum? Or just check the old discuss?


  • 0

    This place is intended to be a learning community via questions and answers. You may want to read the FAQ.

    The old Discuss will be discontinued in the future.


  • 0

    Could you spend some time refining your question so it does sound like a question? With that, other people could understand what you are trying to get to, and may even suggest a better solution and we get to learn something.


  • 0
    W
    This post is deleted!

  • 0
    S
    This post is deleted!

  • -8
    Z

    Well, actually, I just modified one line and got accepted...

                    if(!ret.contains(subset))
                    ret.add(subset);
    

    I'm using Java, so basically just make sure the added subset does not exist in the result before adding it into the result. Yeah it might not be very efficient, but since overall time complexity is O(2^n) which is fairly slow, this line did not hurt the run time too much...


  • 0
    D

    I did it the same way


  • 0
    U

    I did it in python with same idea.

    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integer
        def subsetsWithDup(self, S):
            A = [[]]
            pre, preCount = None, 1
            S.sort()
            for n in S:
                count = len(A)
                if n == pre:
                    count = preCount
                else:
                    pre = n
                    preCount = count
                for i in range(len(A)-count, len(A)):
                    ss = A[i][:]
                    ss.append(n)
                    A.append(ss)
            return A

  • 0
    R

    C++ version:

    class Solution {
    public:
        vector<vector<int> > subsetsWithDup(vector<int> & S) {
            vector<vector<int> > results{{}};
            sort(S.begin(),S.end());
            for(int i=0,next=0;i<S.size();i = next) {
                next = upper_bound(S.begin(),S.end(),S[i])-S.begin();
                for(int j=results.size()-1;j>=0;j--) {
                    for(int p=1;p<=next-i;p++) {
                        vector<int> rpt(p,S[i]);
                        results.push_back( results[j] );
                        results.back().insert(results.back().end(),rpt.begin(),rpt.end());
                    }
                }
            }
            return results;
        }
    };

  • 0
    F

    My python version

    def subsetsWithDup(self, S):
        S.sort()
        res = [[]]
        pre, count = None, 0
        for e in S:
            if e != pre:
                pre,count = e,len(res)
            res = res + [l+[e] for l in res[len(res)-count:]]
        return res
    

  • 4
    T

    Java version:

    public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
    	List<List<Integer>> subsets = new ArrayList<List<Integer>>();
    	subsets.add(new ArrayList<Integer>());
    	if (null == num || num.length == 0)
    		return subsets;
    	quickSort(num, 0, num.length - 1);
    	int j, lastLength = 0;
    	for (int i = 0; i < num.length; i++) {
    		if (i != 0 && num[i] == num[i - 1])
    			j = lastLength;
    		else
    			j = 0;
    		lastLength = subsets.size();
    		for (; j < lastLength; j++) {
    			ArrayList<Integer> temp = (ArrayList<Integer>) subsets.get(j);
    			temp = (ArrayList<Integer>) temp.clone();
    			temp.add(num[i]);
    			subsets.add(temp);
    		}
    	}
    	return subsets;
    }
    
    }

  • 0
    S

    Wish you leave some comments when sharing solution.


  • 0
    S

    Wish you leave some comments when sharing solution.


  • 0
    Y
    This post is deleted!

  • 0
    C

    @fuellee Nice code, btw, res[len(res)-count:] is same as res[-count:]


  • 0
    M

    I did it too!


Log in to reply
 

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