全排列

46. 全排列

来源：力扣（LeetCode） 链接 (opens new window)：https://leetcode.cn/problems/permutations/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

github (opens new window)

问题

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

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

思路

递归+回溯

var permute = function (nums) {
  const res = [],
    path = [];

  function backtracking(n, k, used) {
    if (path.length === k) {
      //递归终止条件
      res.push([...path]);
      return;
    }

    for (let i = 0; i < k; i++) {
      const item = n[i]
      if (used[i]) continue; //已经使用过了就跳过本轮循环
      path.push(item);
      used[i] = true;
      backtracking(n, k, used); //递归

      path.pop(); //回溯 将push进的元素pop出来 然后标记成未使用 继续其他分支
      used[i] = false;
    }
  }

  backtracking(nums, nums.length, []); //调用回溯函数 传入nums，nums长度，used数组

  return res;
};