46. 全排列 I

[luryZhu]

46. 全排列
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    https://leetcode-cn.com/problems/permutations/

思路：

建模成树，节点存储当前已排列好数组 pre
孩子节点：所有可能的下一个数，因为数组无重复数，所以只需要排除掉已经取过就行

如何判断一个数有没有被取过：用一个数组存储，取过就置为true

递归函数：
函数出口：pre长度等于num时，即扫描完所有数，将pre加入解集
函数内容：判断扫描所有可能的孩子，用过的数剪枝，没用过即调用递归

代码

var permute = function(nums) {
    let ret=[]
    let used=[]
    let dfs=(pre)=>{
        if (pre.length===nums.length){
            ret.push(pre)
            return
        }
        for(let i=0;i<nums.length;i++){
            if(used[i]) continue
            used[i]=true
            dfs(pre.concat(nums[i]))
            used[i]=false
        }
    }
    dfs([])
    return ret
};