字符串全排列指的是给定一个字符串，生成该字符串中字符的所有可能排列组合，比如输入字符串"abc"，全排列结果包含"abc"、"acb"、"bac"、"bca"、"cab"、"cba"共6种。使用递归回溯算法可以很清晰地实现这个需求，核心思路是通过递归遍历每个位置的可选字符，交换字符后进入下一层递归，完成当前层排列后回溯恢复字符交换前的状态，避免影响其他排列的生成。
递归回溯实现核心逻辑
实现字符串全排列的递归回溯算法主要包含三个步骤：
- 确定递归终止条件：当当前递归处理的起始位置到达字符串末尾时，说明已经生成了一个完整的排列，将其加入结果集合。
- 遍历可选字符：从当前起始位置到字符串末尾，依次将每个位置的字符与起始位置的字符交换，模拟选择当前位置的字符。
- 回溯操作：交换字符后进入下一层递归处理下一个位置，递归返回后再次交换两个字符，恢复原来的字符串状态，保证后续遍历的正确性。
完整C++代码示例
下面是使用递归回溯实现字符串全排列的完整C++代码，包含去重逻辑，避免字符串中存在重复字符时生成重复的排列结果：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 递归回溯核心函数
// s: 待处理的字符串，start: 当前处理的起始位置，res: 存储结果的集合
void backtrack(string& s, int start, vector<string>& res) {
// 递归终止条件：起始位置到达字符串末尾，说明生成一个完整排列
if (start == s.size()) {
res.push_back(s);
return;
}
// 用于记录当前位置已经使用过的字符，实现去重
vector<bool> used(256, false);
for (int i = start; i < s.size(); i++) {
// 如果当前字符已经在当前位置使用过，跳过避免重复排列
if (used[s[i]]) {
continue;
}
used[s[i]] = true;
// 交换当前位置和起始位置的字符
swap(s[start], s[i]);
// 递归处理下一个位置
backtrack(s, start + 1, res);
// 回溯：交换回来，恢复字符串原来的状态
swap(s[start], s[i]);
}
}
// 对外调用的接口函数
vector<string> getPermutation(string s) {
vector<string> res;
// 先对字符串排序，方便去重逻辑生效
sort(s.begin(), s.end());
backtrack(s, 0, res);
return res;
}
int main() {
string testStr = "abc";
vector<string> permutations = getPermutation(testStr);
cout << "字符串 " << testStr << " 的全排列结果：" << endl;
for (const string& str : permutations) {
cout << str << endl;
}
// 测试有重复字符的情况
string testStr2 = "aab";
vector<string> permutations2 = getPermutation(testStr2);
cout << "n字符串 " << testStr2 << " 的全排列结果（去重后）：" << endl;
for (const string& str : permutations2) {
cout << str << endl;
}
return 0;
}
代码执行流程说明
以输入字符串"abc"为例，递归回溯的执行过程如下：
- 初始调用backtrack，start为0，字符串为"abc"，遍历i从0到2：
- i=0时，交换s[0]和s[0]（无变化），进入start=1的递归。
- start=1时，遍历i从1到2：i=1交换s[1]和s[1]，进入start=2的递归；start=2时遍历i从2到2，交换后进入start=3的递归，触发终止条件，将"abc"加入结果；回溯后恢复字符串为"abc"，i=2时交换s[1]和s[2]，字符串变为"acb"，进入start=2的递归，最终将"acb"加入结果，回溯恢复为"abc"。
- 回到start=0的循环，i=1时交换s[0]和s[1]，字符串变为"bac"，后续递归会生成"bac"、"bca"两个排列。
- i=2时交换s[0]和s[2]，字符串变为"cba"，后续递归会生成"cba"、"cab"两个排列。
最终所有递归执行完成，就得到了字符串"abc"的全部6种排列结果。
算法复杂度分析
对于长度为n的无重复字符字符串，全排列的总数是n的阶乘，因此时间复杂度为O(n*n!)，其中n!是生成所有排列的数量，每个排列生成需要O(n)的时间复制到结果集合中。空间复杂度方面，递归栈的深度最大为n，结果集合存储所有排列需要O(n*n!)的空间，去重使用的used数组大小为256，属于常数空间。
注意事项
- 如果字符串中存在重复字符，必须加入去重逻辑，否则会生成重复的排列结果，上述代码中使用used数组记录当前位置已经使用过的字符，配合先排序的操作，可以有效去重。
- 回溯操作是递归回溯算法的核心，每次递归返回后必须恢复交换前的字符状态，否则会影响后续其他分支的排列生成。
- 如果不需要存储所有排列结果，只是需要逐个输出，可以在递归终止条件处直接输出当前字符串，减少空间占用。