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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let result = [];
  let used = [];

  function backtrack(track) {
    // 结束条件
    if (track.length == nums.length) {
      // 位置1:利用es6的'... 展开运算符'进行浅拷贝
      result.push([...track]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // 跳过本次循环
      track.push(nums[i]);
      used[i] = true;
      backtrack(track);
      track.pop(); // 删除路径
      used[i] = false;
    }
  }

  backtrack([]);

  return result;
};

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

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 *
 * ! 不同于全排列1 这里需要考虑重复的情况，所以回溯的时候加入
 * ! nums[i] == nums[i - 1] && !visited[i - 1] 进行判断（需要对数组先行排序）
 *
 */
var permuteUnique = function (nums) {
  let result = [],
    len = nums.length,
    visited = new Array(len).fill(false); // 用于剪枝

  nums.sort((a, b) => a - b); // 排序

  function backtrack(path) {
    // 判断终止条件
    if (path.length === len) {
      result.push(path.slice());
      return;
    }

    for (let i = 0; i < len; i++) {
      if (visited[i] || (nums[i] == nums[i - 1] && !visited[i - 1])) continue; // 跳过

      // 加入当前数字并置状态位为已加入选择
      path.push(nums[i]);
      visited[i] = true;
      // 继续回溯
      backtrack(path);

      // 撤销选择并还原状态位
      path.pop();
      visited[i] = false;
    }
  }

  backtrack([]);

  return result;
};

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
  let result = [];
  let visited = [];

  s = s.split('').sort((a, b) => a.charCodeAt() - b.charCodeAt());

  function backtrack(track) {
    if (track.length === s.length) {
      result.push([...track].join(''));
      return;
    }

    for (let i = 0; i < s.length; i++) {
      if (visited[i] || (!visited[i - 1] && s[i] === s[i - 1])) continue;
      track.push(s[i]);
      visited[i] = true;
      backtrack(track);
      track.pop();
      visited[i] = false;
    }
  }

  backtrack([]);
  return result;
};

console.log(permutation('abb'));

输入：s = "a1b2
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function (s) {
  let result = [];
  function dfs(i, str) {
    if (i === s.length) {
      result.push(str);
      return;
    }
    if (/\d/.test(s[i])) dfs(i + 1, str + s[i]);
    else {
      dfs(i + 1, str + s[i].toLowerCase());
      dfs(i + 1, str + s[i].toUpperCase());
    }
  }

  dfs(0, '');

  return result;
};

// 使用回溯
var letterCasePermutation = function (s) {
  let result = [];

  function backtrack(s, idx) {
    result.push(s);
    for (let i = idx; i < s.length; i++) {
      // 数字 跳过
      if (/\d/.test(s[i])) continue;
      // 字母, 反转字母大小写
      s = s.slice(0, i) + reverseStr(s[i]) + s.slice(i + 1);

      backtrack(s, i + 1);

      // 回溯, 将字母大小写反转回来
      s = s.slice(0, i) + reverseStr(s[i]) + s.slice(i + 1);
    }
  }

  function reverseStr(s) {
    return /[a-z]/.test(s) ? s.toUpperCase() : s.toLowerCase();
  }

  backtrack(s, 0);
  return result;
};