# 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
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
@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.
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!
def dfs(self, nums, index, path, res):
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 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)]
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.