字符串的排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

回溯法
也就是利用树去尝试不同的可能性，不断地去字符串数组里面拿一个字符出来拼接字符串，当字符串数组被拿空时，就把结果添加进结果数组里，然后回溯上一层。（通过往数组加回去字符以及拼接的字符串减少一个来回溯。）

代码

// 回溯法
function Permutation(str) {
  let res = [];
  const pStr = '';
  if (str.length <= 0) return res;
  arr = str.split(''); // 将字符串转化为字符数组
  res = permutate(arr, pStr, res);
  return res;
}
function permutate(arr, pStr, res) {
  if (arr.length === 0) {
    return res.push(pStr);
  }
  const isRepeated = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (!isRepeated.has(arr[i])) {
      // 避免相同的字符交换
      const char = arr.splice(i, 1)[0];
      pStr += char;
      permutate(arr, pStr, res);
      arr.splice(i, 0, char); // 恢复字符串，回溯
      pStr = pStr.slice(0, pStr.length - 1); // 回溯
      isRepeated.add(char);
    }
  }

  return res;
}