46 全排列

leetcode链接

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

示例:

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

题解

排列问题和组合问题类似但是有不一样的地方。都是从有限集合中取数，但是全排列是可以在先选择第二位然后再选第一位的。但是组合是选完一位后要移位到下一位（也就是程序里index，以及 i+1的作用）

但是排列是不能用index也不需要用index控制的。我们可以通过两种方案来达到全排列的情况。

第一种，每次选完一次之后，把没选择的单独成数组以供下一轮（递归树下一层）进行选择。 第二种，每次选择后，标识该数字的是否被使用过。

第一种方法-每次循环新数组

var permute = function (nums) {
    var results = []
    var permuteInner = function (nums, result, currentNums) {
        //如果length 相同，可以结束。其实此时currentNums也是length === 0
        if (result.length === nums.length) {
            results.push([...result])
            return
        }
        for (let i = 0; i < currentNums.length; i++) {
            //因为不重复，可以直接过滤出可以选择的
            const newNums = currentNums.filter(one => one !== currentNums[i])
            permuteInner(nums, [...result, currentNums[i]], newNums)
        }
    }

    //初始可选数组是所有数字
    permuteInner(nums, [], nums)

    return results
};

第二种解法-利用used数组

利用used数组，这样可以避免选择到重复的数据。

var permute = function (nums) {
    var results = []
    var permuteInner = function (nums, result, used) {
        if (result.length === nums.length) {
            results.push([...result])
            return
        }
        //从0到n都循环
        for (let i = 0; i < nums.length; i++) {
            //如果递归树上层选过那么就不能选择了
            if (used[i] === false) {
                used[i] = true
                permuteInner(nums, [...result, nums[i]], used)
                used[i] = false
            }
        }
    }

    //定义used 数组
    var used = Array(nums.length).fill(false)

    permuteInner(nums, [], used)

    return results
};