# Python easy to understand solutions (DFS recursively, Bit Manipulation, Iteratively).

• ``````# 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``````

• This post is deleted!

• very good solution thanks, I like the iterative solution

• the iteratively solution is so brilliant! thanks for sharing

• Is the iterative solution O(2^n)? Is the best we can get from iterative?

• I think the answer is: yes. Just because the solution space is that large...

• 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 I don't think you need sort nuts

• This post is deleted!

• Very nice! Code is neat and clean! The bit manipulation is awesome!

• @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 4

Then you do dfs. At the moment of visiting each node, you add the traced path to result.

• @caikehe

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]
``````

• Thanks for sharing! For the iterative solution, I think there is no need to sort.

• @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!

• 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)

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)
``````

• your code is neat!

• Three 1-linear 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)]``````

• @Zura the for loop condition is the ending condition

• I don't think you need to sort the nums

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