LeetCode-46-全排列

一：题目描述：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

二：示例与提示

示例 1:

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

1 2	输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3:

1 2	输入：nums = [1] 输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

三：思路

回溯 + used数组记录

排列与组合的区别
- [0, 2]，[2,0]这是一个组合但是是不同的排列
- 对于原先的组合问题，是为了避免出现上方的这个情况，导致重复使用该元素，才引入startIndex，在每次递归的时候都要+1，避免使用前面使用过的元素
- 但是对于排列来说，这是一个不同的排列，前面的元素，我们后面可以使用
对于这种组合排列问题，先画出树形结构
- 横向拓展是for循环遍历nums数组
- 纵向深度是递归获得排列
- 但我们要避免同一个元素在一个排列中重复使用，因此使用used数组来记录使用过的元素，true使用过，false未使用
- 剩下的思路跟之前的组合问题类似了
终止条件：单个path获取到的元素长度跟nums长度一致就添加到res结果集中
单层逻辑：递归 + 回溯

四：代码 + 复杂度分析

回溯

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    //回溯
    //组合问题
    //抽象成树形结构
    //收集结果的数组
    const res = []
    //收集单条路径的结果
    const path = []
    //used数组避免取重复的元素
    const used = []
    const backtracking = (nums, used) => {
        //终止条件
        if(path.length === nums.length) {
            //把path加入到结果
            // console.log(path)
            res.push([...path])
            return 
        }
        //单层逻辑
        for(let i = 0; i < nums.length; i++) {
            //如果used数组中该位置的元素被标记了 说明已经用过了 就跳过
            if(used[i] === true) continue
            //收集
            path.push(nums[i])
            //标记
            used[i] = true
            //递归
            backtracking(nums, used)
            //回溯
            path.pop(nums[i])
            used[i] = false
        }
    }
    backtracking(nums, used)
    return res
};

时间复杂度：O(n!)
- 在回溯算法中，需要遍历数组的每个元素，并进行递归调用。对于每个元素，都有 n 种选择，因此总共需要进行 n^n 次操作
空间复杂度：O(n!)
- res 数组用于存储所有排列结果，其空间复杂度为 **O(n!)**，因为最多有 n! 个排列结果。