全排列

题目

题目来源：力扣（LeetCode）

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

示例 1：

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

示例 2：

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

示例 3：

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

思路分析

以数组 [1, 2, 3] 的全排列为例。
先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
最后写以 3开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。
总结搜索的方法：按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到 不重不漏。这样的思路，可以用一个树形结构表示。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permute = function(nums) {
  // 保存结果数组，保存每个路径（排列）
  const result = []
  // 调用回溯函数，传入参数
  backtracking(nums, nums.length, [], [])
  // 返回结果数组
  return result
  // 定义回溯递归函数，传入数组，长度，节点是否被使用过的数组
  // used 用来标记节点是否被用过 path 用来存储路径，定义为一个栈
  function backtracking(nums, len, used, path){
    // 递归出口
      // 如果到达叶子节点，将路径推入结果数组，并返回
      if(path.length === len) {
          result.push([...path])
          return
      }
      // 遍历候选字符
      for(let i = 0; i < len; i++){
          // 使用过就下一轮循环
          if(!used[i]){
            // undefind和fasle都会进来
      // 这里说明这个数还没有被使用，入栈path
      path.push(nums[i])
      // 标记这个数被使用过了
      used[i] = true
      // 开始进行递归
      backtracking(nums, len, used, path)
      // 回溯【状态重置】撤销之前的操作
      path.pop()
      used[i] = false
    }
      }
  }
};