全排列-中等

难度：中等

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

示例：

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

解题思路：
利用递归的思想，
（1）任意取一个元素放在第一个位置，则有n种选择；
（2）再剩下的n-1个元素中再取一个元素放在第二个位置则有n-1种选择，此时可以看做对n-1个元素进行全排列；
（3）重复第二步，直到对最后一个元素进行全排列，即最后一个元素放在最后一个位置，全排列结束

var permute = function(arr) {
            let allArr = [];
            let newArr = [];
            const getArr = (data) => {
                let num 
                data.forEach((item, index) => {
                    num = data.splice(index, 1)[0]
                    newArr.push(num)
                    if (data.length === 0 ){
                        allArr.push(newArr.slice())
                    }
                    getArr(data)
                    data.splice(index, 0, num);  // 为了恢复data
                    newArr.pop(); // 为了清空newArr
                });
                return allArr;
            }
            return getArr(arr);
};

function backtrack(list, tempList, nums) {
    if (tempList.length === nums.length) return list.push([...tempList]);
    for(let i = 0; i < nums.length; i++) {
        if (tempList.includes(nums[i])) continue;
        tempList.push(nums[i]);
        backtrack(list, tempList, nums);
        tempList.pop();
    }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const list = [];
    backtrack(list, [], nums)
    return list
};