大家好我西瓜哥，今天做一道比较常考的算法题。

编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

如输入 "qwe"，要求返回 ["qwe", "qew", "wqe", "weq", "ewq", "eqw"] 。

LeetCode 题目链接：

回溯解法

常见的解法是回溯。

我们使用一个 toVisited 数组，用于维护递归过程中尚未访问的字符。

回溯函数的 TypeScript 签名如下：

(combs: string[], s: string, toVisit: string[]) => void

先看下回溯函数的代码实现。

function r(combs, s, toVisit) {  if (toVisit.length === 0) {    combs.push(s);    return;  }  for (let i = 0; i < toVisit.length; i++) {    r(combs, s + toVisit[i], toVisit.filter(item => item != toVisit[i]));  }}

我们会遍历 toVisit 数组，将这些尚未被访问的字符，追加到 s 末尾，然后生成一个新的移除了该字符的 toVisited，作为下一个递归调用的参数。

当所有字符都被访问过了（toVisite 数组为空）时，我们就拿到了一种排列方式，将它放到 combs，然后结束当前的这一个迭代。

当所有的迭代都结束后，我们的 combs 中就包含了所有的排列，将其返回即可。

完整代码实现如下：

function permutation(S: string): string[] {  const combs = [];  r(combs, '', [...S]);  return combs;};function r(combs: string[], s: string, toVisit: string[]) {  if (toVisit.length === 0) {    combs.push(s);    return;  }  for (let i = 0; i < toVisit.length; i++) {    r(combs, s + toVisit[i], toVisit.filter(item => item != toVisit[i]));  }}

我们注意到，每次递归，都要拷贝一份待访问字符数组，即 toVisit.filter(item => item != toVisit[i])，这个效率实在是不怎么高啊。

其实这个可以优化一下。如果你实现过排序算法，比如选择排序，你就会想到一个原地使用原数组的思路。排序算法中将原数组的元素进行交换，分为 “排序区间” 和 “未排序区间”。

我们这里也可以致敬一下，也交换一下嘛，在原数组中原地分为 “已访问字符区间” 和 “待访问数组”。然后在下一个递归函数执行完后，再复原一下数组。

改良后的实现如下：

function permutation(S): string[] {  const combs = [];  r(combs, [...S], 0);  return combs;};function r(combs, chars, first) {  if (first === chars.length) {    combs.push(chars.join(''));    return;  }  for (let i = first; i < chars.length; i++) {    swap(chars, i, first);    r(combs, chars, first + 1);    swap(chars, i, first);  }}function swap(chars, i, j) {  const tmp = chars[i];  chars[i] = chars[j];  chars[j] = tmp;}

本文讲解了如何用回溯的思考解全排列问题，回溯解法的核心思路是每次迭代，从待访问字符集中挑选字符，直到所有字符都被访问完。

为此你需要维护待访问字符集数组，这里如果想要高效一些，可以使用数组原地分区或是使用栈的方式，直接拷贝一份效率很低，但优点是简单直接（所以我做题时经常这么干）

我是每周做五道算法题的前端西瓜哥，欢迎关注我。