# 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)
Simple Python solution (DFS).

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

@shiyan2
The problem lies with the
line.pop()
. If you doprint res
afterline.pop()
, you would see that the num popped from theline
also gets popped from theres
. The possible reason is thatline + [num]
creates a copy of the line whileline.append(num)
doesn't.Using
line + [num]
gives you an advantage that you still keep the originalline
for next iteration so that you don't need to pop the new num out.


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

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 builtin 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 memoryintensive operation of the copying solutions I’ve discussed here, so use it only if the other methods won’t work.

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

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