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
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.
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.