题目

题解

整体思路是从第一个数开始，不断地与后面的数进行交换（这个交换也包括与自己交换，即不交换），每一个数都有s.size()-start种交换方式，当最好一个数交换完毕，加入res种。res用set去重，当s中有重复的字符时res可能有重复的情况。可以参考这里的图示进行理解。

class Solution {//回溯交换法
    set<string> res;//定义set防止出现重复，当有一样的字符的时候可能会有重复的字符
public:
    void dfs(string s, int start){//递归函数，start表示现在递归到第几个字符
        //如果start超限，说明完成一个分支，可以加入到结果res中
        if(start >= s.size()){
            res.insert(s);
            return;
        }
        //递归，先交换然后递归，回溯的时候再将交换的两个数换回来
        for(int i=start; i<s.size(); ++i){//交换的数从start开始往后交换，因为之前的已经交换过了
            swap(s[start],s[i]);
            dfs(s,start+1);//注意这里递归是start+1，因为是用start的下一个数与之后的数进行递归交换
            swap(s[start],s[i]);
        }
    }
    vector<string> permutation(string s) {
        dfs(s,0);//调用递归函数
        return vector<string>(res.begin(),res.end());
    }
};