问题分类：您可以将此问题视为探索性问题，即给定一组输入字符，探索不同的排列方式。
解决方案：回溯算法擅长解决探索性问题，尽管它具有高时间复杂度。为了演示解决方案，请想象一下如何手动解决这个小型输入字符集的问题：
[a, b, c]。
以下是步骤：
- 取最左边的字符。这是索引为0的字符，并将其与目标右字符在索引0交换，即与自身交换。这是因为[a, b, c]本身就是一个有效的排列，因此我们要保留它。交换字符通常需要两个指针，分别指向每个字符。所以我们假设有一个left和right指针。
- 使用相同的最左边的字符（索引为0），将其与目标右字符在索引0 + 1 = 1交换，即将目标右指针向前移动1步。这将给出输出：[b, a, c]
- 使用相同的最左边的字符（索引为0），将其与下一个目标右字符（即索引0 + 1 + 1 = 2）交换。这将给出输出：[c, b, a]
好的，现在我们需要停止，因为没有更多的目标右字符可以与最左边的字符交换了。因此，我们的right指针需要小于input中的最大索引。使用for循环逐步移动right指针，从left索引开始，以输入长度-1结尾。
现在，您需要执行与上述相同的步骤，但移动左指针，使其指向下一个最左边的字符。但保留步骤2和3中的输入。另一种想象这种情况的方式是说：“嘿，我已经完成了最左边的字符。现在我不想再使用它，但我很想继续使用到目前为止的第二个最左边的字符。”
何时停止？当左指针达到输入字符串长度-1时，因为此索引之后没有更多字符。在递归算法（如回溯）中，需要停止的情况称为基本情况。在我们的示例中，基本情况是：left === input.length - 1。
这是一个图形化可视化：
left index| Input String:
-------------------------------------------------------------------------------
left = 0 | in=[a, b, c]
(swap in[0] with in[0]) (swap in[0] with in[1]) (swap in[0] with in[2])
left = 1 | in=[a, b, c] in=[b, a, c] in=[c, b, a]
(swap in[1] with in[1]) (swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2])
left = 2 | [a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, b, a] [c, a, b]
概述：
- 为了将左指针向右移动，我们将使用递归增量。
- 为了将右指针向右移动，我们将使用一个for循环，但是我们需要始终从左指针开始，否则我们将探索我们已经探索过的东西。
回溯算法：
回溯算法的伪代码形式如下：
fun(input)
if(base_case_check(input)) {
} else {
fun(reduce(input))
}
我们的解决方案：
function permutate(string) {
if(!string || string.length === 0)
return new Set(['']);
let left = 0;
let result = new Set();
permutationHelper(string, result, left);
return result;
}
function permutationHelper(string, result, left) {
if(left === string.length-1) {
result.add(string);
} else {
for(let right=left; right < string.length; right++) {
string = swap(string, left, right);
permutationHelper(string, result, left+1);
string = swap(string, left, right);
}
}
}
function swap(string, left, right) {
let tmpString = string.split('');
let tmp = tmpString[left];
tmpString[left] = tmpString[right];
tmpString[right] = tmp;
return tmpString.join('');
}
let input = 'abc';
let result = permutate(input);
let expected = new Set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']);
if(setsEquality(result, expected)) {
console.log('Congrats, you generated all permuations');
} else {
console.log('Sorry, not all permuations are generated');
}
function setsEquality(actualResult, expectedResult) {
if (actualResult.size !== expectedResult.size) {
return false;
}
for (let permutation of actualResult) {
if (!expectedResult.has(permutation)) return false;
}
return true;
}
function assert(condition, desc) {
if (condition) {
console.log(`${desc} ... PASS`);
} else {
console.log(`${desc} ... FAIL`);
}
}
总结和时间复杂度：
- 我们通过交换现有输入字符串中的字符来进行选择
- 当我们将左索引增加1时，我们会探索剩下要探索的内容。事实上，这意味着我们将所有后续递归的输入集合减少1。因此，我们需要完成的工作是：Nx（N-1）x（N-2）x（N-3）x...x1 = N！。然而，由于我们需要使用for循环来在输入中进行探索，所以总时间复杂度为：0(N*N!)
- 我们通过在修改后的输入字符串中交换字符来恢复选择。
function foo(x) { return [ x.substring(0, 1) ].push(foo(x.substring(1))) }- Tibrogargan