大家好我西瓜哥，今天做一道比较常考的算法题。
编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
如输入 "qwe"，要求返回 ["qwe", "qew", "wqe", "weq", "ewq", "eqw"] 。
LeetCode 题目链接：
https://leetcode-cn.com/problems/permutation-i-lcci/
回溯解法
常见的解法是回溯。
我们使用一个 toVisited 数组，用于维护递归过程中尚未访问的字符。
回溯函数的 TypeScript 签名如下：
(combs: string[], s: string, toVisit: string[]) => void
- combs：字符串数组。排列组合被保存的数组，回溯结束后用于返回
- s：字符串
- toVisit：尚未访问的字符数组。
先看下回溯函数的代码实现。
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; }
结尾
本文讲解了如何用回溯的思考解全排列问题，回溯解法的核心思路是每次迭代，从待访问字符集中挑选字符，直到所有字符都被访问完。
为此你需要维护待访问字符集数组，这里如果想要高效一些，可以使用数组原地分区或是使用栈的方式，直接拷贝一份效率很低，但优点是简单直接（所以我做题时经常这么干）
我是每周做五道算法题的前端西瓜哥，欢迎关注我。
