Permutations

题目

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3]have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路分析

这道题的思路应该也是要用到DFS，首先把所有的长度为3的数组都产生出来，包括使用重复的数字。然后在调用递归函数之前把含有重复数字的数组过滤掉，这样既能过滤含有重复数字的数组，又能减少运算复杂度

有两种方法来过滤含有重复数字的数组

• 判断当前的数字是不是已经包含在path数组中了

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(nums, length, lastnum, path, result):
            if length == 0:
                result.append(path)
                return
            for i in range(0, len(nums)):
                if nums[i] in path: continue  <<<<<<<这句话是作filer用的
                dfs(nums, length-1, nums[i], path+[nums[i]], result)
        len_nums = len(nums)
        result = []
        dfs(nums, len_nums, 0, [], result)
        return result

• 使用visited数组来判断当前数字是不是已经在上一层递归前中被使用了

这个方法的原理是可以用如下简化图示意：

上一层使用的元素： 1

当前层调用递归函数将要使用的元素： 1 2 3

本来当前层要使用数组中所有的数组，即1，2，3，但是因为上一层调用递归函数前使用的元素是1，那么我们就不能在掉用递归函数的时候使用1了，这样就可以避免同一个元素在一个排列数组中被多次使用。

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(nums, length, visited, path, result):
            if length == 0:
                result.append(path)
                return
            for i in range(0, len(nums)):
                if visited[i]: continue
                visited[i] = True   <<<< 当前数字设置为True，说明它被当前递归函数使用了
                dfs(nums, length-1, visited, path+[nums[i]], result)
                visited[i] = False  <<<< 调用完递归函数后，要对上一层的数字的visited属性reset
        len_nums = len(nums)
        result = []
        visited = len_nums * [False]   <<<< 初始化visited数组，数组中的所有数字都没有被访问过
        dfs(nums, len_nums, visited, [], result)
        return result