Leetcode 46.全排列

Posted on |

46.全排列

题目

给定一个没有重复数字的序列，返回其所有可能的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

方法

方法1：回溯法

给定一个没有重复元素的序列，本问题可以考虑n叉树（n=len(nums)），回溯点就是深度（temp长度）等于n（nums长度）时，回溯条件就是当前元素已经出现在temp中了（全排列不能出现重复元素）

  • res用来存储所有的返回所有排列，tep用来生成每个排列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution(object):
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res=[]
            self.backtrack(nums, res, [])
            return res

        def backtrack(self, nums, res, temp):
            if len(temp)==len(nums):      # quit loop 回溯条件
                res.append(list(temp))
            else:
                for n in nums:
                    if n in temp:         # cut duplicate
                        continue          # 如果在当前排列中已经有n了，就continue，相当于分支限界，即不对当前节点子树搜寻了
                    temp.append(n)
                    self.backtrack(nums, res, temp)
                    temp.pop()            # 把结尾的元素用nums中的下一个值替换掉，遍历下一颗子树

方法2：剑指offer 字符串的排列

复杂问题分解：数组看成由两部分组成的，第一部分是第一个元素，第二部分是后面所有元素。求整个数组的排列，可以分为两步：

  • 第一步，求所有可能出现在第一个位置的元素，即把第一个元素和后面所有元素交换
  • 第二步，固定第一个元素，求后面所有元素的排列。此时，仍然把后面的数组分为两部分：后面元素的第一个元素，以及这个元素之后的所有元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        self.helper(nums,0,len(nums))
        return self.res

    def helper(self,nums,position,end):
        if position==end:
            self.res.append(list(nums))
        else:
            for i in range(position,end):
                nums[i],nums[position]=nums[position],nums[i]
                self.helper(nums,position+1,end)
                nums[i],nums[position]=nums[position],nums[i]

做法是把对字符串中的每个元素都当做起始位置，把其他元素当做以后的位置，然后再同样的进行操作。这样就会得到全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        self.dfs(nums, res, [])
        return res
    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
        else:
            for i, n in enumerate(nums):
                self.dfs(nums[:i]+nums[i+1:], res, path+[n])