Is there a better solution?


  • 0
    Y

    I made a function to generate all the subsets of a length of k. Then I called this function n times with the k increased from 1 to n (n is the length of the array S). Is there a better solution? It seems we could make some uses of the generated subsets. For example, when we have all the subsets of k=1, could we use them to generate the subsets of k=2? Thanks.


  • 15
    U

    Sure, and the implementation is straightforward.

    class Solution:
    # @param S, a list of integer
    # @return a list of lists of integer
    def subsets(self, S):
        A = [[]]
        S.sort()
        for n in S:
            for i in range(len(A)):
                ss = A[i][:]
                ss.append(n)
                A.append(ss)
        return A

  • 1
    S

    This is the C++ version with similar idea of @us917.

    class Solution {
    public:
        vector<vector<int> > subsets(vector<int> &S) {
            // 1: sort the array
            // 2: each time, add in one new number to all previous sets
            vector <vector<int> > sets;
            sort(S.begin(), S.end());
            vector<int> set;
            sets.push_back(set);
            for (auto i:S) {
                int cur_size = sets.size(); // corrected after @cecilulysess's reminder
                for (int j = 0; j < sets.size(); j++) {
                    set = sets[j];
                    set.push_back(i);
                    sets.push_back(set);
                }
            }
            
            return sets;
        }
    };

  • 0
    C

    this will show memory limit exceed


  • 0
    C

    A correct C++ version according to @us917's idea.

    The key problem for C++ is, you have to have a fixed loop size for the inner for

    class Solution {
    public:
        vector<vector<int> > subsets(vector<int> &S) {
            sort(S.begin(), S.end());
            vector<vector<int>> res;
            vector<int> d;
            int curr_size = 0;
            res.push_back(vector<int>{});
            for (int &e : S) {
                curr_size = res.size();
                for(int i = 0; i < curr_size; ++i) {
                    d = res[i];
                    d.push_back(e);
                    res.push_back(d);
                }
            }
            return res;
        }
    };

  • 0
    S

    You are right. My previous solution was exactly as what you said... I carelessly modified my code before I posted it in that I forgot the function of the fixed size.


  • 0
    F

    here is my solution:

    def subsets(self, S):
        res = [[]]
        S.sort()
        for e in S:
            res = res+[l+[e] for l in res]
        return res
    

  • 1
    H

    we can use stl::set to sort while insert. I got AC in 20m.

    class Solution {
    private:
        void ctsbst(vector<vector<int> > &ret, set<int> &row, vector<int> &S, int n)
        {
            if(n == S.size())
            {
                vector<int> v;
                set<int>::iterator it;
                for(it = row.begin(); it != row.end(); ++it)
                    v.push_back(*it);
                ret.push_back(v);
                return;
            }
            row.insert(S[n]);
            ctsbst(ret, row, S, n+1);
            row.erase(S[n]);
            ctsbst(ret, row, S, n+1);
        }
    public:
        vector<vector<int> > subsets(vector<int> &S) {
            vector<vector<int> > ret;
            set<int> row;
            ctsbst(ret, row, S, 0);
            return ret;
        }
    };
    

  • 2
    P

    Just four lines of Python code:

    def subsets(self, S):
        R = [[]]
        for s in sorted(S):
            R += [r+[s] for r in R]
        return R

  • 0
    Z

    Hey, us917! Could you please explain what does [:] do in line 9? What's wrong with only ss = A[i]? Thanks!


  • 0
    S

    It is a complete copy of list. It is same as ss = list(A[i]). Check out this page


  • 0
    O

    From you solution, I think it will take approximately O(n^2) time. Is there any better solution? Thanks in advance.


  • 0
    P

    IMAO this problem will take O(2^n) since there are 2^n subsets. (The size of the inner for loop is changing over time.) Surprise me if I am wrong.


  • 0
    Z
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 5
    Z
    //dynamic programming
    class Solution {
        public:
        	vector<vector<int> > subsets(vector<int> &S) {
        		vector<vector<int>> re;		
        		sort(S.begin(),S.end());
        		re.push_back(vector<int>());
        		for(int i=0;i<S.size();++i)
        		{
        			int size=re.size();
        			for(int j=0;j<size;++j)
        			{
        				//vector<int> tmp=re[j];
        				//tmp.push_back(S[i]);
        				re.push_back(re[j]);
        				re[re.size()-1].push_back(S[i]);
        			}
        		}
        		return re;
        	}
        };
    

    @us917 Your method is not efficient enough in that in each iteration ss is a copy of a former element and to add it into A, another copy is needed. Copy costs a lot of time. So my method is better because only one copy is needed to add one element. But in fact, my method is not better than recursion, even worse. For the solution of 18 elements in S, recursion costs about 4.7 seconds,and my method costs about 5.6 seconds, and your method costs about 8 seconds. But I still don't know why.Anybody can figure out?


  • 0
    Z

    this method is worse than recursion. you can have a look at @zhshuai1 's answer.


  • 0
    M

    can anyone please explain what " auto i:S " does in the code?
    I am sorry. I am unfamiliar with this kind of usage of auto keyword.


  • 0
    J

    Thanks! The vector is always changing.


  • 0
    J

    A solution similar to @hongzhi's std::set method:

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int> &S) {
            sort(S.begin(), S.end());  // dirty
            vector<vector<int>> powerset;
            vector<int> subset;
            collectSubsets(S, 0, subset, powerset);
            return powerset;
        }
        void collectSubsets(vector<int> &S, int n, vector<int> &subset, vector<vector<int>> &powerset) {
            if (n < S.size()) {
                subset.push_back(S[n]);
                collectSubsets(S, n+1, subset, powerset);
                subset.pop_back();
                collectSubsets(S, n+1, subset, powerset);
            } else {
                powerset.push_back(subset);
            }
        }
    };

Log in to reply
 

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