欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 46. 全排列

程序员文章站 2022-03-08 13:17:03
46. 全排列 题目来源: "https://leetcode cn.com/problems/permutations/" 题目 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 解题思路 思路:深度优化搜索 先看题目,以所给数组 [1, 2, 3] 的全排列为例: 以 1 开始, ......

46. 全排列


题目来源:

题目


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

示例:

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

解题思路


思路:深度优化搜索

先看题目,以所给数组 [1, 2, 3] 的全排列为例:

  • 以 1 开始,全排列有:[1,2,3], [1,3,2];
  • 以 2 开始,全排列有 [2,1,3], [2,3,1];
  • 以 3 开始,全排列有 [3,1,2], [3,2,1]。

从上面的情况,可以看出。枚举每个每一位可能出现的情况,已选择的数字在下面的选择则不能出现。按照这个做法,所有的情况将能够罗列出来。这里其实就是执行一次深度优先搜索,从根节点到叶子节点形成的路径就是一个全排列。

按照这种思路,沿用上面的例子,从空列表 [] 开始,以 1 开始为例。现在确定以 1 开始,则列表为 [1],现在选择 [2][3] 之中的一个,先选 2,最后剩下的只有数字 3,所以形成全排列 [1, 2, 3]

已知还有一种情况,也就是 [1, 3, 2],那么如何实现从 [1, 2, 3][1, 3, 2] 的变化。深度优先搜索是如何实现的?其实是从 [1, 2, 3] 回到 [1, 2] 的情况,撤销数字 3,因为当前层只能选择 3,所以再撤销 2 的选择,这样后面的程序则能在选择 3 的时候后续也能选择 2。

代码实现


class solution:
    def permute(self, nums: list[int]) -> list[list[int]]:

        def _dfs(nums, depth, pmt, be_selected, length, ans):
            # 表示深度优化搜索的深度等于数组长度时,这个时候表示全排列已经生成
            # 也就是符合情况的选择已经选择完毕
            # 将这个全排列的情况添加到列表中
            # 这里需要注意,pmt 在参数传递是引用传递,拷贝一份添加到结果中
            if depth == length:
                ans.append(pmt[:])
                return

            # 开始遍历
            for i in range(length):
                # be_selected,表示原数组中的元素的状态,是否被选择,是为 true,否为 false
                if not be_selected[i]:
                    # 当元素被选择时,改变状态
                    be_selected[i] = true
                    # 将元素添加到 pmt 中,以构成后续
                    pmt.append(nums[i])
                    # 向下一层进行遍历
                    _dfs(nums, depth + 1, pmt, be_selected, length, ans)
                    # 遍历结束时,进行回溯,这个时候状态要进行重置
                    # 如上面说的 `[1, 2, 3]` 到 `[1, 3, 2]` 中变化,要撤销 3,再撤销 2,重新选择
                    # 状态改变
                    be_selected[i] = false
                    # 撤销
                    pmt.pop()

        length = len(nums)
        if length == 0:
            return []

        be_selected = [false] * length
        ans = []
        _dfs(nums, 0, [], be_selected, length, ans)
        return ans

实现结果


LeetCode 46. 全排列


以上就是使用深度优化搜索的思想,解决《46. 全排列》的问题的主要内容,主要需要注意的是状态重置。


欢迎关注微信公众号《书所集录》