Description

找到数组全排列

Solution

暴力dfs with sort
Time O(N! *N logN)

import copy
class Solution(object):
    def dfs(self,pre_fix,n_set):
        if len(n_set) ==0:
            self.res.append(copy.deepcopy(pre_fix))
            return 
        iter = list(n_set)
        iter.sort()
        for s in iter:
            pre_fix.append(s)
            n_set.remove(s)
            self.dfs(pre_fix,n_set)
            n_set.add(s)
            pre_fix.pop()
            
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.set = set(nums)
        self.res = []
        self.dfs([],self.set)
        return self.res

重写更general的dfs

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if nums is None:
            return []
        if len(nums)<=1:
            return [nums]
        self.res=[]
        self.dfs(nums,[])
        return self.res
    def dfs(self,nums,trace):
        if len(nums)==0:
            self.res.append(trace)
            return
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:],trace+[nums[i]])