# DFS recursively
def subsets1(self, nums):
res = []
self.dfs(sorted(nums), 0, [], res)
return res
def dfs(self, nums, index, path, res):
res.append(path)
for i in xrange(index, len(nums)):
self.dfs(nums, i+1, path+[nums[i]], res)
# Bit Manipulation
def subsets2(self, nums):
res = []
nums.sort()
for i in xrange(1<<len(nums)):
tmp = []
for j in xrange(len(nums)):
if i & 1 << j: # if i >> j & 1:
tmp.append(nums[j])
res.append(tmp)
return res
# Iteratively
def subsets(self, nums):
res = [[]]
for num in sorted(nums):
res += [item+[num] for item in res]
return res
Python easy to understand solutions (DFS recursively, Bit Manipulation, Iteratively).


I've learned so much reading through your clear and concise solutions  thank you!
I've been looking through many of your DFS solutions, and I was hoping you could explain why you start xrange at "index" and increment the index on each recursive call. In your solution to "Permutations" you start xrange at 0 each time and don't increment an index in your recursive calls. The problems and your solutions to them are similar in many ways, I just can't wrap my head around why we need to increment the index at each recursive call.
Any insight you can provide would be much appreciated. Thanks again!

@jandkdev Yes, I found it is actually hard to arrange an applicable DFS. It would be wonderful if you could share a little bit of how you design the algorithms.


@caikehe's dfs solution:
Try to build a directed graph in which node x connects to node y (y > x). For example, if the given set is [0,1,2,3,4], then:
node 0 is connected to node 1, 2, 3, 4
node 1 is connected to node 2,3,4
node 2 is connected to node 3,4
node 3 is connected to node 4Then you do dfs. At the moment of visiting each node, you add the traced path to result.

Here's an iterative version that accounts for duplicates.
We keep the result in a set instead of a list to prevent duplicates. To do this we need to store the results as tuples, which we cast back to lists before returning. Note the interesting syntax needed to create a tuple of length 1
def subsets(self, nums): res = set([()]) for num in sorted(nums): res.update([item+(num, ) for item in res if item+(num, ) not in res]) return [list(item) for item in res]

@caikehe Hi caikehe, would you please do me a favor by analyzing the time and space complexity of your third implementation (the iterative method)? Thank you very much in advance!

said in Python easy to understand solutions (DFS recursively, Bit Manipulation, Iteratively).:
def dfs(self, nums, index, path, res):
res.append(path)
for i in xrange(index, len(nums)):
self.dfs(nums, i+1, path+[nums[i]], res)for your dfs
why dont you have to check the ending condition or backtracking condition?def dfs(self, nums, index, path, res): res.append(path) for i in xrange(index, len(nums)): self.dfs(nums, i+1, path+[nums[i]], res)

Three 1linear python solutions, pick your favourite:
def subsets(self, nums): return reduce(lambda L, ele: L + [l + [ele] for l in L], nums, [[]]) def subsets(self, nums): [[x for x in l if x is not None] for l in itertools.product(*zip(nums, [None] * len(nums)))] def subsets(self, nums): [l for n in range(len(nums) + 1) for l in itertools.combinations(nums, n)]
