字符串的排列

题解:

考察点：深度优先搜索，回溯，剪枝

易错点：

字符串中的字母有重复，直接使用全排列生成的字符串会有重复，需要通过剪枝或者等手段去重。

方法一：回溯+去重

回溯法是一种深度优先搜索中常用的一种手段，基本思想是首先按选设定条件进行深度搜索，当探索到某一步时，发现原先搜索的路径并不满足，就退回上一步重新选择。在全排列问题中，首先设置一个指针，代表当前生成的字符串中的元素个数，设置一个数组表示每个位置是否被访问过，然后按照从前往后的顺寻，选择未被访问过的字母进入字符串，每次被选择的位置把标记为已访问，在进行深度优先搜索之后再将标记释放，进行回溯。注意，因为字母有重复，因此生成的全排列也会有重复，需要进行去重。

#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(set<string>&res,string ans,vector<int> num,int pos){
    if(pos==num.size()){
        res.insert(ans);
    }
    for(int i=0;i<num.size();i++){
        if(!vis[i]){
            vis[i]=1;
            ans.push_back(num[i]+'a');
            dfs(res,ans,num,pos+1);
            vis[i]=0;
            ans.pop_back();
        }
    }
}
int main()
{
    cin>>s;
    vector<int>num;
    for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
    set<string>res;
    string ans="";
    dfs(res,ans,num,0);
    int tmp=0;
    int len=res.size();
    for(auto s:res){
        ++tmp;
        if(tmp==1){
            cout<<"["<<s<<", ";
        }else if(tmp==len){
            cout<<s<<"]"<<endl;
        }else{
            cout<<s<<", ";
        }
    }
    return 0;
}

方法二：回溯+剪枝

可以对上述方法进行改进，由于有重复字母存在，可以考虑生成答案的过程中对重复字母进行剪枝。对于两个重复元素，在全排列中交换其位置不会生成新的排列，基于这个思想，首先会对字母进行排序，这样确保重复元素相邻。那么假设当前位置为，在枚举排列的时候，保证当前位置的字母和之前的一样，并且之前的字母没有被标记，则可以把这种情况剪枝掉。

#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(vector<string>&res,string ans,vector<int> num,int pos){
    if(pos==num.size()){
        res.push_back(ans);
    }
    for(int i=0;i<num.size();i++){
        if(!vis[i]){
            if(i>0&&num[i]==num[i-1]&&!vis[i-1]) continue;
            vis[i]=1;
            ans.push_back(num[i]+'a');
            dfs(res,ans,num,pos+1);
            vis[i]=0;
            ans.pop_back();
        }
    }
}
int main()
{
    cin>>s;
    vector<int>num;
    for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
    sort(num.begin(),num.end());
    vector<string>res;
    string ans="";
    dfs(res,ans,num,0);
    for(int i=0;i<res.size();i++){
        if(i==0){
            cout<<"["<<res[i]<<", ";
        }else if(i==res.size()-1){
            cout<<res[i]<<"]"<<endl;
        }else{
            cout<<res[i]<<", ";
        }
    }
    return 0;
}