打印给定字符串的所有排列
打印给定字符串的所有排列是回溯问题的一个示例。我们将减小子字符串的大小以解决子问题，然后再次回溯以从该部分获得另一个排列。
例如，如果字符串是ABC，则所有排列将是ABC，ACB，BAC，BCA，CAB，CBA。
该算法的复杂度为O（n！）。这是一个巨大的复杂性。当字符串大小增加时，需要更长的时间才能完成任务。
输入输出
Input: A string “ABC” Output: All permutations of ABC is: ABC ACB BAC BCA CBA CAB
算法
stringPermutation(str, left, right)
输入： 字符串和字符的左右索引。
输出：打印字符串的所有排列。
Begin
if left = right, then
display str
else
for i := left to right, do
swap str[left] and str[i]
stringPermutation(str, left+1, right)
swap str[left] and str[i] //for backtrack
done
End示例
#include<iostream>
using namespace std;
void stringPermutation(string str, int left, int right) {
if(left == right)
cout << str << endl;
else {
for(int i = left; i<= right; i++) {
swap(str[left], str[i]);
stringPermutation(str, left + 1, right);
swap(str[left], str[i]); //swap back for backtracking
}
}
}
int main() {
string str = "ABC";
cout << "All permutations of " << str << " is: " <<endl<<endl;
stringPermutation(str, 0, str.size()-1);
}输出结果
All permutations of ABC is: ABC ACB BAC BCA CBA CAB