常考算法题无重复字符串的排列组合

　　大家好我西瓜哥，今天做一道比较常考的算法题。
　　编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
　　如输入qwe，要求返回〔qwe，qew，wqe，weq，ewq，eqw〕。
　　LeetCode题目链接：
　　https：leetcodecn。comproblemspermutationilcci回溯解法
　　常见的解法是回溯。
　　我们使用一个toVisited数组，用于维护递归过程中尚未访问的字符。
　　回溯函数的TypeScript签名如下：（combs：string〔〕，s：string，toVisit：string〔〕）voidcombs：字符串数组。排列组合被保存的数组，回溯结束后用于返回s：字符串toVisit：尚未访问的字符数组。
　　先看下回溯函数的代码实现。functionr（combs，s，toVisit）｛if（toVisit。length0）｛combs。push（s）；return；｝for（leti0；itoVisit。length；i）｛r（combs，stoVisit〔i〕，toVisit。filter（itemitem！toVisit〔i〕））；｝｝
　　我们会遍历toVisit数组，将这些尚未被访问的字符，追加到s末尾，然后生成一个新的移除了该字符的toVisited，作为下一个递归调用的参数。
　　当所有字符都被访问过了（toVisite数组为空）时，我们就拿到了一种排列方式，将它放到combs，然后结束当前的这一个迭代。
　　当所有的迭代都结束后，我们的combs中就包含了所有的排列，将其返回即可。
　　完整代码实现如下：functionpermutation（S：string）：string〔〕｛constcombs〔〕；r（combs，，〔。。。S〕）；returncombs；｝；functionr（combs：string〔〕，s：string，toVisit：string〔〕）｛if（toVisit。length0）｛combs。push（s）；return；｝for（leti0；itoVisit。length；i）｛r（combs，stoVisit〔i〕，toVisit。filter（itemitem！toVisit〔i〕））；｝｝
　　我们注意到，每次递归，都要拷贝一份待访问字符数组，即toVisit。filter（itemitem！toVisit〔i〕），这个效率实在是不怎么高啊。
　　其实这个可以优化一下。如果你实现过排序算法，比如选择排序，你就会想到一个原地使用原数组的思路。排序算法中将原数组的元素进行交换，分为排序区间和未排序区间。
　　我们这里也可以致敬一下，也交换一下嘛，在原数组中原地分为已访问字符区间和待访问数组。然后在下一个递归函数执行完后，再复原一下数组。
　　改良后的实现如下：functionpermutation（S）：string〔〕｛constcombs〔〕；r（combs，〔。。。S〕，0）；returncombs；｝；functionr（combs，chars，first）｛if（firstchars。length）｛combs。push（chars。join（））；return；｝for（letifirst；ichars。length；i）｛swap（chars，i，first）；r（combs，chars，first1）；swap（chars，i，first）；｝｝functionswap（chars，i，j）｛consttmpchars〔i〕；chars〔i〕chars〔j〕；chars〔j〕tmp；｝结尾
　　本文讲解了如何用回溯的思考解全排列问题，回溯解法的核心思路是每次迭代，从待访问字符集中挑选字符，直到所有字符都被访问完。
　　为此你需要维护待访问字符集数组，这里如果想要高效一些，可以使用数组原地分区或是使用栈的方式，直接拷贝一份效率很低，但优点是简单直接（所以我做题时经常这么干）
　　我是每周做五道算法题的前端西瓜哥，欢迎关注我。