Straight-forward iterative solution:
def subsets(self, nums): subsets = [] for n in sorted(nums): subsets += [s + [n] for s in subsets] return subsets
Same thing but with
reduce instead of the loop:
def subsets(self, nums): return reduce(lambda subsets, n: subsets + [s+[n] for s in subsets], sorted(nums), [])
combinations from the library:
def subsets(self, nums): return [s for n in range(len(nums)+1) for s in itertools.combinations(sorted(nums), n)]
Using integers as bit mask to tell which elements to use in a subset:
def subsets(self, nums): nums.sort() return [[nums[i] for i in range(len(nums)) if mask >> i & 1] for mask in range(2 ** len(nums))]
@StefanPochmann Hi StefanPochmann, your solutions are so clever. At the same time, would you please do me a favor by analyzing the time and space complexity of your first implementation (the iterative method)? Thank you very much in advance!
I have thought about using bit mask. Your bit solution is clear but it is also much slower than your other solutions. Could it be more efficient?
N = 20, 0.25s for combinations solution.
N = 20, 1s for reduce solution.
N = 20, 0.7s for my product solution.
def subsets(self, nums): return [filter(None, l) for l in itertools.product(*zip(nums, [None] * len(nums)))]
@lee215 A big reason why the
combinations solution is so fast is that it returns a list of tuples instead of lists like it's supposed to. Turning them into lists makes that solution about as fast as the
I think the bit mask solution is so slow because I'm building every list from scratch element by element and in my own Python code. It's just much faster to add one element to an existing list. I don't think there's much one can do without significantly altering the solution. Here's one that's about as fast as the
reduce solutions, though:
def subsets(self, nums): n = len(nums) subsets = [] * 2**n for i in xrange(n): subsets[1 << i] = [nums[i]] for mask in xrange(1, 2**n): subsets[mask] = subsets[mask & -mask] + subsets[mask & mask-1] return subsets
And here's one that's super fast, returns instantly because it's lazy:
def subsets(self, nums): class FakeList(list): def __len__(self): return 2**len(nums) def __getitem__(self, mask): return [num for i, num in enumerate(nums) if mask >> i & 1] return FakeList()
Btw, your solution is wrong and doesn't even get accepted. For input
 you return
[,] instead of
It was embarrassing. I correct it.
def subsets(self, nums): return [filter(lambda x: x != None, l) for l in itertools.product(*zip(nums, [None] * len(nums)))]
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.