1、解题思路

这是一个字符串的全排列问题，提到全排列我们肯定首先想到递归。这道题的思路就是我们先固定住一个位置，去求剩余字符的全排列。而这道题的难点在于：对于"abb"这类的字符串，我们递归的去求剩余字符的全排列时得到的结果会出现重复的。所以我们采用set容器来去除重复的结果。

2、基础知识

2.1 set容器介绍

set的特性是。所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。set不允许两个元素有相同的键值。因此set中的元素没有重复的。

set底层的实现是红黑树。

2.2 swap函数介绍

c++提供了一种用于交换的swap函数， swap 包含在命名空间std 里面。它是一个模板函数，其定义是：

由于传入的是引用，因此我们操作的是原字符串哦！

3、代码实现

class Solution {
public:
	void fPerm(int pos,string s,set<string>&ret)
	{
		if(pos+1==s.length()) //因为s.length是长度，下标最多能访问到长度-1，因此这里是pos+1
		{
			ret.insert(s);
			return;
		}

		for(int i =pos;i<s.length();++i)
		{
			swap(s.at(pos),s.at(i));  //固定出第一个元素
			fPerm(pos+1,s,ret); //求剩下元素的全排列
			swap(s.at(pos),s.at(i)); //要恢复字符串原始的序列
		}
	}
    vector<string> Permutation(string str) {
    	set<string> ret;
        //判空
        if(str.size()==0) return {};
        fPerm(0,str,ret);
        return vector<string>({ret.begin(),ret.end()}); //拷贝构造vector
    }
};