Simple Python solution (DFS).


  • 38
    C
    # DFS
    def permute(self, nums):
        res = []
        self.dfs(nums, [], res)
        return res
        
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            # return # backtracking
        for i in xrange(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

  • 3

    can someone plz tell me why this code generate empty "res" variable? Everything is the same as except using append/pop for passing the DFS. Even the "line" variable before appending to "res" is correct.

    Does it have something to do with referencing? The only thing I could think of is whatever passed to res got cleaned up. I would really appreciate if someone could show me the link to reference.

    class Solution(object):
    def dfs(self, nums, res, line):
        if not nums:
            print(line)
            res.append(line)
            return
    
        for i, num in enumerate(nums):
            line.append(num)
            # self.dfs(nums[:i]+nums[i+1:], res, line+[num])  
            self.dfs(nums[:i]+nums[i+1:], res, line)
            line.pop()
    
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, res, [])
        print(res)
        return res

  • 2
    L

    @shiyan2

    The problem lies with the line.pop(). If you do print res after line.pop(), you would see that the num popped from the line also gets popped from theres. The possible reason is that line + [num]creates a copy of the line while line.append(num) doesn't.

    Using line + [num] gives you an advantage that you still keep the original line for next iteration so that you don't need to pop the new num out.


  • 0
    D

    @leros1 Thank you so much. I was banging my head over this.


  • 0
    L

    @leros1 hi here is hard to understand. do you know where to find the detail explanation (books/internet) of this tech point? thanks.


  • 0
    J

    Would someone please do me a favor by analyzing the time and space complexity of the implementation? Thank you very much in advance!


  • 0
    L

    @shiyan2
    Actually you could just change line 5 from res.append(line) to res.append(line[:]) and it will work well because when using line[:], it means you clone a new list line and append it to res.


  • 0
    C

    @leonard_cohen

    Search for "Copying Structures (and Basic Memory Management)". Below is some notes I saw online. Hope it helps.

    Since it’s so easy to make a list in Python, one might think copying it is also straightforward. When I was first starting out with the language, I would often try to make separate copies of lists using simple assignment operators.

    list1 = [1,2,3,4,5]
    list2 = list1
    list2.append(6)
    list2
    [1, 2, 3, 4, 5, 6]

    list1
    [1, 2, 3, 4, 5, 6]

    Notice what happens? I make list1 and try to make list2 be a copy of that list via assignment. But if I modify list2, such as by adding in the number 6, it also modifies list1! This is a deceptive but important point. Making lists equal to other lists will essentially create two variable names pointing to the same list in memory. This will apply to any ‘container’ item, such as dictionaries.

    Since simple assignment does not create distinct copies, Python has a built-in list statement, as well as generic copy operations. It’s also possible to perform copies using slicing. Some solutions are shown below.

    list3 = list(list1)
    list1
    [1, 2, 3, 4, 5, 6]

    list3
    [1, 2, 3, 4, 5, 6]

    list3.remove(3)
    list3
    [1, 2, 4, 5, 6]

    list1
    [1, 2, 3, 4, 5, 6]

    import copy
    list4 = copy.copy(list1)

    And what if one containers within containers?

    If changes one of those dictionaries, that change would be reflected in all larger dictionaries.

    The solution to this is to use the deepcopy method, which will copy everything. This is the most memory-intensive operation of the copying solutions I’ve discussed here, so use it only if the other methods won’t work.


  • 0
    L

    @jessicalee Looks like a O(n!) solution. (If someone thinks it's O(n*n!) please explain your reasoning)


  • 0
    C
    This post is deleted!

  • 2
    P

    Elaborate on some explanations. Thanks for your solution.

    class Solution(object):
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res = []
            lev, avail, lev_node = 0, nums, []
            N = len(nums)
            def dfs(lev, avail, lev_node):
                if lev == N:
                    res.append(lev_node)
                    return
                for i in range(len(avail)):
                    dfs(lev+1, avail[:i]+avail[i+1:], lev_node+[avail[i]])
            
            dfs(lev, avail, lev_node)
            return(res)
    
    lev:      level of tree, i.e. the length of node
    avail:    elements available to be combined to form new child node
    lev_node: node content
    dfs(lev, avail, lev_node)
    dfs(0, [1,2,3], [])
    |- dfs(1, [2,3], [1])
        |- dfs(2, [3], [1,2])
            |- ...
        |- dfs(2, [2], [1,3])
            |- dfs(3, [], [1,3,2])
                |- no more
    |- dfs(1, [1,3], [2])
        |- ...
    |- dfs(2, [1,2], [3])
        |- ...
    

Log in to reply
 

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