方法一：库函数

1.解题思路

题意：
对于给定字符串，找出它的全排列。
分析：
考察回溯算法

2.解法

这里可使用库函数next_permutation()得到字符串全排列，依次加入数组存储即可

3.具体代码

class Solution {
public:
    vector<string> Permutation(string str) {
        sort(str.begin(),str.end());
        vector<string>ans;
        ans.push_back(str);
        while (next_permutation(str.begin(), str.end())){//使用库函数
            ans.push_back(str);
        } 
        return ans;         
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：，字符串全排列总数共,而一次排列用时
空间复杂度：，仅用到vector保存n!个全排列。

方法二：交换回溯

1.解题思路

将字符串转化为字符数组，接着进行交换回溯。每次从根结点到叶子结点的序列即为原序列的一个排列。

2.解法

递归中首先固定某一个下标对应元素，然后将其他元素进行交换。
到叶子节点后返回，接着i++,u比i小1，i与其后面一个元素交换。
注意要用set去重，例如aa，回溯过程会会出现两次aa，所以用set去重后，再加入ans即可。

3.图解

4.具体代码

class Solution {
public:
    set<string>s;
    void dfs(int u,string &a,int n){//u:当前遍历到字符，a:字符串，n:字符串长度
        if(u>n){//递归边界，到达字符串尾
            string b;//将当前遍历序列保存为字符串
            for(int i=1;i<=n;i++){
                b+=a[i];
            }
            s.insert(b);//字符串加入set容器
            return;
        }
        for(int i=u;i<=n;i++){//遍历序列
            swap(a[i],a[u]);
            dfs(u+1,a,n);//到叶子节点后，u比i小1，i与其后面一个元素交换 
            swap(a[i],a[u]);
        }
    }
    vector<string> Permutation(string str) {
        for(int i=str.size();i>=1;i--){//将字符串转化为字符数组，方便接下来操作
            str[i]=str[i-1];
        }
        dfs(1,str,str.size());//str.size()是str的最后一个元素 
        vector<string>ans;
        for(set<string>::iterator it=s.begin();it!=s.end();it++){//set去重后加入ans
            ans.push_back(*it);
        }
        return ans; 
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：，字符串全排列总数为n!，而递归中嵌套了一个长度为n的循环，所以时间复杂度为O(n*n!)
空间复杂度：，用到了一个大小为n!的set容器及数组。