【LeetCode 46】全排列

偏执的太偏执、 2022-12-06 04:23 142阅读 0赞

#### 题目描述 ####

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

示例:

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

#### 解题思路 ####

这个题目很容易理解，就是将数组中的所有数进行全排列，最后输出全排列的结果。

这个应该还是回溯+剪枝的问题，以1为开头的组合为例：  
![在这里插入图片描述][20200912144251971.png]  
红色部分就是我们需要剪掉的枝。限制条件就是，结果数组不能重复，元素不能重复。

这里我们初始化一个数组arr，当每一次将一个元素放入结果数组中时，就将其在arr中标记为true。这样，下一次在往里面加其他元素时，查找该元素，就可以避免元素的重复。

实际上，JavaScript为我们提供了 `find()`方法来查找是否存在某个元素。那为什么我们还要整的这么复杂，用arr来保存数据呢？因为，`find()`方法的时间复杂度为O(n)，所以我们使用arr来保存已经遍历过的元素。这样就用空间换了时间，降低了时间复杂度。

时间复杂度为O(n)，空间复杂度为O(n)。

#### 代码实现 ####

/** * @param {number[]} nums * @return {number[][]} */
    var permute = function(nums) { 
        const res = []  // 保存最后的结果
        const arr = []  // 将这条路径上已有的元素保存为true，避免元素重复
    
        const dfs = (path) => { 
            if(path.length === nums.length){ 
                res.push([...path])
                return
            }
    
            for(let num of nums){ 
                if(arr[num]) continue  // 如果已经存在这个数，就跳过
                path.push(num) 
                arr[num] = true
                dfs(path)
                path.pop()
                arr[num] = false
            }
        }
        dfs([])
        return res
    };

#### 提交结果 ####

![在这里插入图片描述][20200912142727563.png]

[20200912144251971.png]: /images/20221123/32f11d109df34f1e834d907eaaad5fb6.png?
[20200912142727563.png]: /images/20221123/45e5cf46a41043b09a8d6aa7d3576ffa.png?