leetcode-数组的全排列的所有结果思路与代码

深藏阁楼爱情的钟 2023-06-18 08:58 11阅读 0赞

### 文章目录 ###

*   *  问题描述
     *  问题分析
     *  问题解法

## 问题描述 ##

问题链接：https://leetcode.com/problems/permutations/  
给定一个不包含重复元素的整数集合，返回全排列的所有结果

leetcode，medium  
46：Permutations

> Given a collection of distinct integers, return all possible permutations.

## 问题分析 ##

既然是全排列，首先想到暴力求解法，但是明显不合适，那呆写很多层for循环，无法想象。

对于这种问题，最简便的方法就是递归求解法，因为数组（输入的集合可以以数组形式输入）中的每个元素可以同等对待，而且每个元素都可能处于最终排列的任意位置。因此，瓷器的解法也是递归解法。这里提供两种解法：

**解法1思路**：从原数组中拿出来一个元素（pop掉），append进全排列数组中，直到原数组的所有元素都被拿出来，则此时全排列数组成为所有输出结果数组中一个。

**解法2思路**：将原数组的第一个元素拿出来（pop掉），加入到全排列数组中，但是跟思路1不同的是，思路1直接加入到全排列数组的最后，而这里是分别加入到全排列数组的每一个可能的位置，例如全排列数组当前的元素数量是5个，那么有6个位置可以加入新的元素，例如下图中，在1之前、1跟3之间、3跟6之间、6跟2之间、2跟7之间、7之后都可以加入新的元素，因此就有6种结果。

## 问题解法 ##

解法1代码如下：

def permutations(nums):
        def fun(nums_fun, path, res):
            if not nums_fun:
                return res.append(path)
            for i in range(0, len(nums_fun)):
                fun(nums_fun[:i] + nums_fun[i+1:], path + [nums_fun[i]], res)
        res = []
        n = len(nums)
        fun(nums, [], res)
        return res

解法2代码如下：

def permutations(nums):
        def fun1(nums_fun1, insert_res):
            if len(nums_fun1) == 0:
                res.append(insert_res)
            else:
                for j in range(0, len(insert_res) + 1):
                    fun1(nums_fun1[1:] if len(nums_fun1) > 1 else [], insert_res[:j] + [nums_fun1[0]] + insert_res[j:])
        res = []
        n = len(nums)
        fun1(nums, [])
        return res

测试代码如下：

if __name__ == "__main__":
        nums = [1, 2, 3]
        print(permutations(nums))