问题分类：您可以将此问题视为一个探索问题，即，给定一组输入字符，探索您可以如何安排它们的不同方式。
解决方案： 回溯算法擅长解决探索性问题，尽管它的时间复杂度很高。为了演示一个解决方案，想象一下您将如何针对一小组输入字符手动解决这个问题：[a, b, c]。
以下是步骤：
- 取最左边的字符。这是索引 0 处的字符并将其与索引 0 处的目标右侧字符交换，即与自身交换。这是因为[a, b, c]本身就是一个有效的排列，因此我们想保留它。交换字符通常需要两个指向每个字符的指针。所以我们可以说，我们将有一个左和右指针。
- 使用相同的最左边的字符（在索引 0 处）与在索引 0 + 1 = 1 处的目标右边字符进行交换，即，将目标右边的指针进一步移动 1 步。这将为您提供输出：[b, a, c]
- 使用同一个最左边的字符（在索引 0 处）与下一个目标右边字符（即索引 0 + 1 + 1 = 2）进行交换。这将为您提供输出：[c, b, a]
好的，现在我们需要停止，因为没有更多的目标右侧字符要与最左侧的字符交换。所以我们的右指针需要保持小于输入中的最大索引。一次一步移动右指针，我们可以使用从左索引开始并以输入长度 - 1 结束的for循环。
现在您需要从上面执行完全相同的步骤，但移动左指针，使其指向最左边的下一个字符。但是，保留第 2 步和第 3 步的输入。想象这种情况的另一种方法是说：'嘿，我已经完成了最左边的字符。现在我不想再使用它了，但我很想继续使用到目前为止我所拥有的结果中的第二个。
我们什么时候停止？当左指针已达到输入字符串的长度 - 1 时，' 因为此索引之后没有更多字符。在递归算法（例如回溯）中，需要停止的情况称为base case。在我们的示例中，基本情况是：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)) {
//do final step
} else {
//choose
fun(reduce(input)) //explore
//un-choose
}
我们的解决方案：
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) {
//base case
result.add(string);
} else {
//recursive case
for(let right=left; right < string.length; right++) {
string = swap(string, left, right); //choose
permutationHelper(string, result, left+1); // explore
string = swap(string, left, right); //unchoose
}
}
}
function swap(string, left, right) {
let tmpString = string.split('');
let tmp = tmpString[left];
tmpString[left] = tmpString[right];
tmpString[right] = tmp;
return tmpString.join('');
}
/* End of solution */
/* Tests */
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!)
- 我们通过在修改后的输入字符串中交换字符来恢复我们的选择