[C++知识库]JZ38* 字符串的排列

题目来源：字符串的排列_牛客题霸_牛客网 (nowcoder.com)?

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n < 10n<10
要求：空间复杂度?O(n!)O(n!)，时间复杂度?O(n!)O(n!)

输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。

示例：

输入："ab"

返回值：["ab","ba"]

说明：返回["ba","ab"]也是正确的

代码：

class Solution {
public:
    void perm(int pos, string str, set<string> &ret){
        if(pos+1 == str.size()){
            ret.insert(str);
            return;
        }
        for(int i=pos; i<str.size(); i++){
            cout<<pos<<"    "<<i<<endl;
            swap(str[pos],str[i]);
            perm(pos+1,str,ret);//pos的值不改变
            swap(str[pos],str[i]);
        }
    }
    vector<string> Permutation(string str) {
        if(str.empty()) return {};
        set<string> ret;
        perm(0,str,ret);//找到所有的排列
        return vector<string>({ret.begin(),ret.end()});//返回vector型
    }
};