[回溯]面试题38. 字符串的排列（medium）

字符串的排列（medium）"/>

[回溯]面试题38. 字符串的排列（medium）

题目：

题解：

• 回溯的基本框架，其中索引index用来表示需要进行排列的次数，直到index==n表示我们已经生成一个排列了。

代码如下：

class Solution {
public:vector<bool> visit;vector<string> permutation(string s) {if(s.empty())return {};set<string> res;visit.resize(s.size(),false);string str;backtrack(s,res,str,0,(int)s.size());return vector<string> (res.begin(),res.end());}//回溯法基本框架：index用来表示使用字符使用的次数，直到使用了n个字符，表示我们已经生成一个排列了//visit用来标记字符是否已经使用，没有使用的字符可以使用void backtrack(string& s,set<string>& res,string& str,int index,int n){if(index>=n)res.insert(str);for(int i=0;i<n;++i){if(!visit[i]){//choose过程：将i号字符加入排列visit[i]=true;str.push_back(s[i]);//进行下一次回溯：index表示回溯的次数，index+1表示进行下一次回溯backtrack(s,res,str,index+1,n);//unchoose过程：将i号字符移除排列str.pop_back();visit[i]=false;}}}
};