65ms python solution with explanation


  • 3
    B

    For any given set S, each element in S can be only either selected or unselected.

    If an S contains n elements, the solution will contains 2^n sets. Can be solution number from 0 -- 2^n - 1

    Each element (eg. the i's element) be selected or not can be represented by the i's bit of the solution number

    class Solution:
        # @param S, a list of integer
        # @return a list of lists of integer
        def subsets(self, S):
            solutions = []
            S.sort()
            bits = len(S)
            for i in range(1 << bits):
                solution = []
                for j in range(bits):
                    if i & (1 << j):
                        solution.append(S[j])
                solutions.append(solution)
            
            return solutions

  • 0
    P

    Is the time complexity still n*2^n?


  • 0
    B

    Yes, because the lower bound of the question is O(N*2^N). For any set S, the number of subsets is 2^N. Since it wants all of it. And for generate any subset, you need to detect any element. This solution is just using iteration so that avoid of recursion.


  • 0
    P

    Thank you very much.


  • 0
    C

    This is so clear and smart! Better than my clumsy DP solution with the same time complexity!

    I made two lists to progress from taking 1 elemnets subsets to taking n elements subsets, while list[i] means using only the first i+1 elements in the sorted input for the subset making, and each round I collect the last subsets from the list into results. This is so clumsy compared to your bit model!

    class Solution:
        # @param S, a list of integer
        # @return a list of lists of integer
        def subsets(self, S):
        	S=sorted(S)
            n=len(S)
            results=[[]]
            baseList=[[[S[j]] for j in xrange(i+1)] for i in xrange(n)]
            progList=[[] for i in xrange(n)]
            for element in xrange(1,n):
            	results+=baseList[n-1]
    
            	for i in xrange(element,n):
            		progList[i]=progList[i-1]+[shortList+[S[i]] for shortList in baseList[i-1]]
            	baseList=progList
            	progList=[[] for i in xrange(n)]
            results+=baseList[n-1]
    
    
            return results
    

  • 0
    L

    I find that it's hard for me to transform recursion to iteration. Thanks for your answer.


Log in to reply
 

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