题目描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

题解

图示引自:NumPy

代码

void permutation(int pos, string str, set<string>& s) {
    //递归出口
    if (pos + 1 == str.length()) {//当
        s.insert(str);
        return;
    }
    // for循环和swap的含义：对于“ABC”，
    // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
    // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
    // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
    for (int i = pos; i < str.length(); i++) {
        swap(str[pos], str[i]);
        permutation(pos + 1, str, s);
        swap(str[pos], str[i]);
        // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
        // 然后进行第三次交换，才能得到"CBA"
    }
}
vector<string> Permutation(string str) {
    if (str.size() == 0) return {};
    set<string> s;
    permutation(0, str, s);
    vector<string> v;
    for (set<string>::iterator it = s.begin(); it != s.end(); it++) {
        v.push_back((*it));
    }
    return v;
}