LeetCode(46)：全排列

题目描述

image

解题思路

在写代码之前，思考以下3个问题：

1. 如何判断是否已经满足结束条件？
2. 如何在选择列表中选择一个？
3. 如何撤销选择？

对全排列这个问题进行具体分析，逐一击破：

1、如何判断是否已经满足结束条件？

显然，每一种全排列的长度 与 题目给定的数组长度一致
因此，只需要比较路径的长度 与 题目给定的数组长度即可

2、如何在选择列表中选择一个？

从广义上说，选择列表就是题目给的数组
从狭义上说，因为题目要求“没有重复”，所以我们需要在选择列表中 剔除那些 已经被包含在路径中的
所以我们就用Set来标记当前路径中存在的元素（保证O(1)的时间复杂度）
每选择一个，就将其加入路径和Set中

3、如何撤销选择？

很简单，从路径中 以及 从Set中删除它即可

代码实现(JavaScript)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const res = new Array()
    const used = new Set()

    var dfs = function(path) {
        
        if(path.length === nums.length){
            res.push(path.slice())
            return
        }

        for(let i=0;i<nums.length;i++){
            if(used.has(nums[i])){
                continue
            }
            path.push(nums[i])
            used.add(nums[i])
            dfs(path)
            path.pop()
            used.delete(nums[i])
        }
    }

    dfs([])
    return res
};