leetcode 46 permutation

先看一道permutation
leetcode 46
Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

简单的写法：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        self.res = []

        def DFS(path, nums):
            if not nums:
                self.res.append(path)
                return
            for i in range(len(nums)):
                DFS(path+[nums[i]], nums[:i]+nums[i+1:])

        DFS([], nums)
        return self.res

发现这题和机器人运动范围 矩阵中的路径都很像
也可以看成是之前走过的节点不要再走的问题
所以这里再使用hash存放之前走过的路径
加深对hash表的认识

class Solution_hash(object):
    def permute(self, nums):
        if not nums:
            return [[]]

        self.res = []
        self.hash = {}

        def DFS(path):
            if len(path) == len(nums):
                self.res.append(path)
                return
            for i in range(len(nums)):
                if i not in self.hash:
                    self.hash[i] = 1
                    DFS(path + [nums[i]])
                    self.hash.pop(i)
        DFS([])
        return self.res