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


  • 83
    C
    # 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

  • 0
    G
    This post is deleted!

  • 1
    W

    very good solution thanks, I like the iterative solution


  • 1
    P

    the iteratively solution is so brilliant! thanks for sharing


  • 0
    P

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


  • 1

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


  • 1
    J

    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!


  • 0

    @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.


  • 0
    C

    @caikehe I don't think you need sort nuts


  • 0
    This post is deleted!

  • 0
    R

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


  • 0
    C

    @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.


  • 1
    W

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

  • 0
    T

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


  • 0
    J

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


  • 0

    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)
    

  • 0
    X

    your code is neat!


  • 1

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

  • 0
    A

    @Zura the for loop condition is the ending condition


  • 0
    M

    I don't think you need to sort the nums


Log in to reply
 

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